求助,调了好久了,为什么这个会TLE,用的双BFS
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
#define MAXSIZE 21
char Graph[MAXSIZE][MAXSIZE];
bool visBox[MAXSIZE][MAXSIZE] = {false};
bool visPerson[MAXSIZE][MAXSIZE] = {false};
int R,L;
struct Node{
int pr,pl;
int br,bl;
string Ans;
};
int dir[5] = {-1,0,1,0,-1};//北,东,南,西
char walk[4] = {'n','e','s','w'};
char push[4] = {'N','E','S','W'};
string path;
bool InMap(int x,int y){
return (x >= 0 && x < R && y >= 0 && y < L);
}
bool BFS2(int startx,int starty,int endx,int endy,string & Tempans,int br,int bc){ //计算人是否可以到达某个点
memset(visPerson,0,sizeof(visPerson));
int nx,ny,x,y;
string tempans;
queue<Node> PersonQueue;
Node handle,Tempnode;
visPerson[br][bc] = true; //你不能走箱子所在的格子
handle.Ans = "",handle.pr = startx,handle.pl = starty;
PersonQueue.push(handle);
while(!PersonQueue.empty()){
Tempnode = PersonQueue.front();
PersonQueue.pop();
x = Tempnode.pr,y = Tempnode.pl,tempans = Tempnode.Ans;
if (x == endx && y == endy){
Tempans = tempans;
return true;
}
visPerson[x][y] = true;
for(register int direct = 0;direct < 4;direct++){
nx = x + dir[direct],ny = y + dir[direct+1];
if (InMap(nx,ny) && Graph[nx][ny] != '#' && !visPerson[nx][ny]){
Tempnode.pr = nx,Tempnode.pl = ny,Tempnode.Ans = tempans + walk[direct];
PersonQueue.push(Tempnode);
}
}
}
return false;
}
bool BFS1(int boxR,int boxC,int PersonR,int PersonC){ //判断推箱子
int nextr,nextc,backr,backc;
queue<Node> BoxQueue;
Node node,tempnode;
node.pr = PersonR,node.pl = PersonC,node.br = boxR,node.bl = boxC,node.Ans = "";
BoxQueue.push(node);
while (!BoxQueue.empty()){
node = BoxQueue.front();
BoxQueue.pop();
if (Graph[node.br][node.bl] == 'T'){
path = node.Ans;
return true;
}
visBox[node.br][node.bl] = true;
for(register int direct = 0;direct < 4;direct++){
string TempPath = "";
nextr = node.br + dir[direct],nextc = node.bl + dir[direct+1];
backr = node.br - dir[direct],backc = node.bl - dir[direct+1];
if (InMap(nextr,nextc) && InMap(backr,backc) && Graph[nextr][nextc] != '#' && Graph[backr][backc] != '#' && !visBox[nextr][nextc] &&
BFS2(node.pr,node.pl,backr,backc,TempPath,node.br,node.bl)){
tempnode.Ans = node.Ans + TempPath + push[direct];
tempnode.br = nextr,tempnode.bl = nextc;
tempnode.pr = node.br,tempnode.pl = node.bl;
BoxQueue.push(tempnode);
}
}
}
return false;
}
int main(){
char TempChar;
int pr,pc,br,bc,loop = 1;
while (cin >> R >> L){
if (R == 0 && L == 0){return 1;}
memset(visBox,0,sizeof(visBox));
for(register int i = 0;i < R;i++){
for(register int j = 0;j < L;j++){
cin >> TempChar;
Graph[i][j] = TempChar;
if (TempChar == 'S'){pr = i,pc = j;}
else if (TempChar == 'B'){br = i,bc = j;}
}
}
cout << "Maze #" << loop++ << endl;
if (BFS1(br,bc,pr,pc)){
cout << path << endl;
} else {
cout << "Impossible." << endl;
}
cout << endl;
}
return 1;
}