The doggie found a bone in an ancient maze, which fascinated him a lot. However, when he picked it up, the maze began to shake, and the doggie could feel the ground sinking. He realized that the bone was a trap, and he tried desperately to get out of this maze.
The maze was a rectangle with sizes N by M. There was a door in the maze. At the beginning, the door was closed and it would open at the T-th second for a short period of time (less than 1 second). Therefore the doggie had to arrive at the door on exactly the T-th second. In every second, he could move one block to one of the upper, lower, left and right neighboring blocks. Once he entered a block, the ground of this block would start to sink and disappear in the next second. He could not stay at one block for more than one second, nor could he move into a visited block. Can the poor doggie survive? Please help him. Input：
The input consists of multiple test cases. The first line of each test case contains three integers N, M, and T (1 < N, M < 7; 0 < T < 50), which denote the sizes of the maze and the time at which the door will open, respectively. The next N lines give the maze layout, with each line containing M characters. A character is one of the following:
'X': a block of wall, which the doggie cannot enter;
'S': the start point of the doggie;
'D': the Door; or
'.': an empty block.
The input is terminated with three 0's. This test case is not to be processed.Output：
For each test case, print in one line "YES" if the doggie can survive, or "NO" otherwise. 4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0Sample Output：
NO
YES错误（注意是错误）代码：
#include<iostream>
#include<stdio.h>
#include<queue>
#include<cstring>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
char board[15][15];
bool book[15][15];
int xs,ys,xd,yd;
int ans;
struct data{
int x,y,TP;
};
int FX[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int N,M,T;
int BFS(){
queue<data> Q;
ans=T-abs(xd-xs)-abs(yd-ys);
if(ans<0||ans&1) return 0;
data head;
head.x = xs,head.y = ys,head.TP = 0;
Q.push(head);
while(!Q.empty()){
data TT = Q.front();
if(TT.x == xd && TT.y == yd){
if(TT.TP == T)return 1;
}
Q.pop();
for(int i=0 ; i<4 ; i++){
int xt = TT.x+FX[i][0];
int yt = TT.y+FX[i][1];
if(xt<0 || xt>=N || yt<0 || yt>=M)continue;
if(book[xt][yt] || board[xt][yt] == 'X')continue;
if(xt!=xd||yt!=yd)book[xt][yt] = true;
data mid;
mid.x = xt,mid.y = yt,mid.TP = TT.TP+1;
Q.push(mid);
}
}
return 0;
}
int main(){
while(scanf("%d %d %d",&N,&M,&T) && N|M|T){
memset(book,false,sizeof(book));
for(int i=0 ; i<N ; i++){
scanf("%s",&board[i]);
}
int flag = 0;
for(int i=0 ; i<N ; i++){
for(int i1=0 ; i1<M ; i1++){
if(board[i][i1] == 'S'){
xs = i,ys = i1;
flag++;
}
else if(board[i][i1] == 'D'){
xd = i,yd = i1;
flag++;
}
if(flag == 2)break;
}
if(flag == 2)break;
}
book[xs][ys] == true;
if(BFS())printf("YES
");
else printf("NO
");
}
return 0;
}
这是用BFS写的，讲真，这题应该用深搜，不过因为觉的BFS省时间我开始想都没想直接用的bfs。
这题深搜很简单，所以我就不放代码了（别打我，我承认我一不小心把代码删了，懒的再写了(╯﹏╰)）。
如图，bfs到点（0,2）时会把点（1,2）标记了，这样点（1,3）就用不了了。
这一点真心恶心，搞了半天想不到方法~唉，有一颗逆天的心奈何没实力。这回把这个错误代码贴出来就是想给大家个新思路，如果有哪位大佬想出来的跪求给我发一份~跪谢:)