题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1110
题意：
给一个矩阵，‘X’代表墙壁，‘.’代表空格，‘S’代表起始位置，‘D’代表终点。从起点开始，每个空格只许经过一次，求在规定的时间t的时候，能否正好到达终点。每走一个花费1个单位时间。输入n,m,t，分别代表矩阵的行，列，规定的时间。
思路：
深度优先搜索，从起点开始，按照四个方向搜索，判断某个方向的下一个方格如果不是墙壁的话，就把它标为墙壁，然后从这个点继续往下搜索，如果从这个点往下搜索失败后，就要把这个点标记回原来的空格符号：‘.’。然后尝试下一个方向。直到i == di, j == dj, t == T的时候，表示搜索成功，flag = true; return; 其中si sj 是起点位置，di dj是终点位置，T是当前所花费的时间。
然后还有几处剪枝：如果这个矩阵的空格的数目小于等于时间t，那么不可能成功。这在主函数里面可以剪枝。在dfs的过程中，如果发现剩余的时间小于当前位置到终点的最小距离，可以直接判断搜索失败；如果剩余的时间和当前位置到终点的最小时间的差值是奇数的话，可以判断搜索一定失败，可以剪枝，如果是偶数的话，则可能成功。
今天突然发现，以前写的解题报告太搓了……向kedebug的博客学习，O(∩_∩)O哈哈~加油
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cctype> 6 #include <stack> 7 #include <queue> 8 #include <cmath> 9 #include <algorithm> 10 #define lson l, m, rt<<1 11 #define rson m+1, r, rt<<1|1 12 using namespace std; 13 typedef long long int LL; 14 const int MAXN = 0x3f3f3f3f; 15 const int MIN = -0x3f3f3f3f; 16 const double eps = 1e-9; 17 18 bool flag; 19 char s[9][9]; 20 int t, n, m, si, sj, di, dj; 21 int dir[4][4] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}}; 22 void dfs(int i, int j, int T){ 23 if (i == di && j == dj && T == t){ 24 flag = true; return; 25 } 26 if (i <= 0 || j <= 0 || i > n || j > m) return; 27 int temp = t - T - abs(i-di) - abs(j-dj); 28 if (temp < 0 || temp&1)return; 29 for (int k = 0; k < 4; ++k){ 30 if (s[i+dir[k][0]][j+dir[k][1]] != 'X'){ 31 s[i+dir[k][0]][j+dir[k][1]] = 'X'; 32 dfs(i+dir[k][0], j+dir[k][1], T+1); 33 if (flag) return; 34 s[i+dir[k][0]][j+dir[k][1]] = '.'; 35 } 36 } 37 return; 38 } 39 int main(void){ 40 #ifndef ONLINE_JUDGE 41 freopen("zoj2110.in", "r", stdin); 42 #endif 43 while (~scanf("%d%d%d", &n, &m, &t) && m+n+t){ 44 getchar(); 45 int wall = 0; 46 for (int i = 1; i <= n; ++i){ 47 for (int j = 1; j <= m; ++j){ 48 scanf("%c", &s[i][j]); 49 if (s[i][j] == 'S'){ 50 si = i; sj = j; 51 } 52 else if (s[i][j] == 'D'){ 53 di = i; dj = j; 54 } 55 else if (s[i][j] == 'X') wall++; 56 } 57 getchar(); 58 } 59 if (m * n - wall <= t){ 60 printf("NO\n"); continue; 61 } 62 flag = false; 63 s[si][sj] = 'X'; 64 dfs(si, sj, 0); 65 if (flag) printf("YES\n"); 66 else printf("NO\n"); 67 } 68 69 return 0; 70 }
开始敲的有错误，怎么也找不出来，然后急了，重新写了一遍，对了……代码能力，准确度有木有！！
还有一点，就是这种读字符的题目，并且是一个一个字符读的，每行要用一个getchar()吸收换行符。并且读字符之前也要用一个getchar()吸收之前读数字的换行符，这个地方特别容易出错。