題目：http://acm.hdu.edu.cn/showproblem.php?pid=1010

?

奇偶性剪枝

?

可以把map看成這樣：?

?

0?1?0?1?0?1?

1?0?1?0?1?0?

0?1?0?1?0?1?

1?0?1?0?1?0?

0?1?0?1?0?1?

?

從為0的格子走一步，必然走向為1的格子，從為1的格子走一步，必然走向為0的格子。?

?

即：

0?->1或1->0?必然是奇數(shù)步??????????

0->0?走1->1?必然是偶數(shù)步

?

所以當遇到從0走向0但是要求時間是奇數(shù)的，或者從1走向0但是要求時間是偶數(shù)的都可以直接判斷不可達！

?

#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h>using namespace std; const int N = 15;char map[N][N]; int startx,starty,endx,endy; int n,m,Time; bool flag;int dir[4][2] = {-1,0,1,0,0,-1,0,1};void DFS(int x,int y,int t) {if(flag) return;if(x == endx && y == endy && t == Time){flag = 1;return;}int tmp = abs(x - endx) + abs(y - endy);if((Time - t) % 2 != tmp % 2) return;if(tmp > Time - t) return;for(int i=0;i<4;i++){int tx = x + dir[i][0];int ty = y + dir[i][1];if(tx < n && tx >= 0 && ty < m && ty >= 0 && map[tx][ty] != 'X'){map[tx][ty] = 'X';t++;DFS(tx,ty,t);t--;map[tx][ty] = '.';}} }int main() {while(cin>>n>>m>>Time){if(n == 0 && m == 0 && Time == 0) break;int cnt = 0;for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>map[i][j];if(map[i][j] == 'S'){startx = i;starty = j;map[i][j] = 'X';}else if(map[i][j] == 'D'){endx = i;endy = j;}else if(map[i][j] == '.') cnt++;}}if(cnt + 1 < Time){puts("NO");continue;}flag = false;DFS(startx,starty,0);if(flag) puts("YES");else puts("NO");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的迷宫搜索的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。