TLE求助!!!
查看原帖
TLE求助!!!
1088320
Mr_Nobody_楼主2023/10/27 17:53

求助,调了好久了,为什么这个会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;
}
2023/10/27 17:53
加载中...