学步园

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

题目大意：这道题就是讲有一只狗要吃骨头，结果进入了一个迷宫陷阱，迷宫里每走过一个地板费时一秒，该地板就会在下一秒塌陷，所以你不能在该地板上逗留。迷宫里面有一个门，只能在特定的某一秒才能打开，让狗逃出去。现在题目告诉你迷宫的大小和门打开的时间，问你狗可不可以逃出去，可以就输出YES,否则NO。

解题思路：这道题，要用到剪枝搜索来做，否则会超时。剪掉的条件是，如果可走地板数目小于给定的时间，绝对不可能得救。还有就是狗走到门的时间必须和题目给定的时间是同奇同偶的，否则也不能在指定的那秒到达门，也不可能得救，剪掉这两种情况后。就用DFS来做。从起点出发，DFS周围的路，走过的路就标记为不可走，一只搜索下去，如果是一条不归路（就是活不了啦）就回溯，把可能的路都搜索一遍过去，看看是否有可行方案。

#include <stdio.h><br /> #include <stdlib.h><br /> #define size 10<br /> bool status;<br /> int DogX,DogY,DoorX,DoorY;<br /> int M,N,T;<br /> int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};//设置四个方向，分别是左、右、下、上<br /> char maze[size][size];<br /> void BFS(int x,int y,int t)<br /> {<br /> int dx,dy;<br /> int i;<br /> if(t == T&&x == DoorX&&y == DoorY)<br /> status = true;<br /> if(status)<br /> return ;<br /> if((abs(DoorX-x)+abs(DoorY-y))%2!=(T-t)%2)<br /> return ;<br /> for (i=0;i<4;i++)<br /> {<br /> dx = x+dir[i][0];<br /> dy = y+dir[i][1];<br /> if (dx>=0&&dx<M&&dy>=0&&dy<N&&maze[dx][dy]!='X')<br /> {<br /> maze[dx][dy] = 'X';<br /> BFS(dx,dy,t+1);<br /> maze[dx][dy] = '.';//此方向如果不行的话就回溯<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> int i,j;<br /> int num;//统计地板数<br /> while (scanf("%d%d%d%*c",&M,&N,&T)!=EOF)<br /> {<br /> if(M==0&&N==0&&T==0)<br /> break;<br /> num = 0;<br /> status = false;<br /> for (i=0;i<M;i++)<br /> {<br /> for (j=0;j<N;j++)<br /> {<br /> scanf("%c",&maze[i][j]);<br /> if (maze[i][j] == 'S')<br /> {<br /> DogX = i;<br /> DogY = j;<br /> }<br /> else if (maze[i][j] == 'D')<br /> {<br /> DoorX = i;DoorY = j;<br /> num++;<br /> }<br /> else<br /> num++;<br /> }<br /> getchar();<br /> }<br /> maze[DogX][DogY]='X';//狗所在的地方下次就一定不能走了<br /> if(num>=T)//可走地板数小于时间，门肯定没法开。<br /> BFS(DogX,DogY,0);<br /> if(status)<br /> printf("YES/n");<br /> else<br /> printf("NO/n");<br /> }<br /> return 0;<br /> }