Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 60673 Accepted
Submission(s): 16589
#include<iostream> #define MAX 10 using namespace std; char maze[MAX][MAX]; int sx, sy, ex, ey, n, m, t; int dx[4] = { 0, 0, 1, -1 }, dy[4] = { 1, -1, 0, 0 }; bool out = false; bool dfs(int x, int y, int sum){ if (sum > t)return false; if (sum == t&&x == ex&&y == ey){ out = true; return true; } if (out)return true; //奇偶剪枝 int temp = abs(ex - x) + abs(ey - y); if (temp % 2 != (t - sum) % 2)return false; for (int i = 0; i < 4; i++){ int nx = x + dx[i], ny = y + dy[i]; if (0 <= nx&&nx < n && 0 <= ny&&ny < m&&maze[nx][ny] != ‘X‘){ maze[nx][ny] = ‘X‘; dfs(nx, ny, sum + 1); maze[nx][ny] = ‘.‘; } } return false; } int main() { while (cin >> n >> m >> t){ if (n + m + t == 0)break; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ cin >> maze[i][j]; if (maze[i][j] == ‘S‘){ sx = i; sy = j; } if (maze[i][j] == ‘D‘){ ex = i; ey = j; } } } maze[sx][sy] = ‘X‘; out = false; //奇偶剪枝 int temp = abs(ex - sx) + abs(ey - sy); if (temp % 2 != t % 2){ cout << "NO" << endl; continue; } for (int i = 0; i < 4; i++){ int x = sx + dx[i], y = sy + dy[i]; if (!out&&0 <= x&&x < n && 0 <= y&&y < m&&maze[x][y] != ‘X‘){ maze[x][y] = ‘X‘; dfs(x, y, 1); maze[x][y] = ‘.‘; } } if (out){ cout << "YES" << endl; } else{ cout << "NO" << endl; } } return 0; }
原文:http://www.cnblogs.com/littlehoom/p/3560398.html