少部分样例MLE求助,有大佬来帮帮我这个蒟蒻吗
查看原帖
少部分样例MLE求助,有大佬来帮帮我这个蒟蒻吗
363149
X_X_M楼主2022/4/17 16:49
#include <bits/stdc++.h>
using namespace std;

short n,m;
short teleport[200][4];
char maze[301][301];
bool memo[301][301];

queue<short> bfsx;
queue<short> bfsy;

void bfs(short step,int count){
    int count2=0;
    for(int i=1;i<=count;i++){
        int x=bfsx.front(),y=bfsy.front();
        bfsx.pop();
        bfsy.pop();
        if(maze[x][y]=='='){
            cout << step;
            return;
        }
        if(x>=1 && (maze[x-1][y]=='.' || maze[x-1][y]=='=') && memo[x-1][y]==0){
            bfsx.push(x-1);
            bfsy.push(y);
            count2++;
            memo[x-1][y]++;
        }
    	if(x<=m && (maze[x+1][y]=='.' || maze[x+1][y]=='=') && memo[x+1][y]==0){
            bfsx.push(x+1);
            bfsy.push(y);
            count2++;
            memo[x+1][y]++;
        }
        if(y>=1 && (maze[x][y-1]=='.' || maze[x][y-1]=='=') && memo[x][y-1]==0){
            bfsx.push(x);
            bfsy.push(y-1);
            count2++;
            memo[x][y-1]++;
        }
        if(y<=m && (maze[x][y+1]=='.' || maze[x][y+1]=='=') && memo[x][y+1]==0){
            bfsx.push(x);
            bfsy.push(y+1);
            count2++;
            memo[x][y+1]++;
    	}
        if(x>=1 && maze[x-1][y]>='A' && maze[x-1][y]<='Z'){
            if(teleport[maze[x-1][y]][0]==x-1 && teleport[maze[x-1][y]][1]==y && memo[x-1][y]<=1){
                bfsx.push(teleport[maze[x-1][y]][2]);
                bfsy.push(teleport[maze[x-1][y]][3]);
            }else if(memo[x-1][y]<=1){
                bfsx.push(teleport[maze[x-1][y]][0]);
                bfsy.push(teleport[maze[x-1][y]][1]);
            }
            count2++;
            memo[x-1][y]++;
        }
        if(x<=m && maze[x+1][y]>='A' && maze[x+1][y]<='Z'){
            if(teleport[maze[x+1][y]][0]==x+1 && teleport[maze[x+1][y]][1]==y && memo[x+1][y]<=1){
                bfsx.push(teleport[maze[x+1][y]][2]);
                bfsy.push(teleport[maze[x+1][y]][3]);
            }else if(memo[x+1][y]<=1){
                bfsx.push(teleport[maze[x+1][y]][0]);
                bfsy.push(teleport[maze[x+1][y]][1]);
            }
            count2++;
            memo[x+1][y]++;
        }
        if(y>=1 && maze[x][y-1]>='A' && maze[x][y-1]<='Z'){
            if(teleport[maze[x][y-1]][0]==x && teleport[maze[x][y-1]][1]==y-1 && memo[x][y-1]<=1){
                bfsx.push(teleport[maze[x][y-1]][2]);
                bfsy.push(teleport[maze[x][y-1]][3]);
            }else if(memo[x][y-1]<=1){
                bfsx.push(teleport[maze[x][y-1]][0]);
                bfsy.push(teleport[maze[x][y-1]][1]);
            }
            count2++;
            memo[x][y-1]++;
        }
        if(y<=n && maze[x][y+1]>='A' && maze[x][y+1]<='Z'){
            if(teleport[maze[x][y+1]][0]==x && teleport[maze[x][y+1]][1]==y+1 && memo[x][y+1]<=1){
                bfsx.push(teleport[maze[x][y+1]][2]);
                bfsy.push(teleport[maze[x][y+1]][3]);
            }else if(memo[x][y+1]<=1){
                bfsx.push(teleport[maze[x][y+1]][0]);
                bfsy.push(teleport[maze[x][y+1]][1]);
            }
            count2++;
            memo[x][y+1]++;
        }
    }
    bfs(step+1,count2);
}

int main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> maze[i][j];
            if(maze[i][j]=='@'){
                bfsx.push(i);
                bfsy.push(j);
            }
            if(maze[i][j]>='A' && maze[i][j]<='Z'){
                if(teleport[maze[i][j]][0]==0){
                    teleport[maze[i][j]][0]=i;
                    teleport[maze[i][j]][1]=j;
                }else{
                    teleport[maze[i][j]][2]=i;
                    teleport[maze[i][j]][3]=j;
                }
            }
        }
    }
    bfs(0,1);
    return 0;
}
2022/4/17 16:49
加载中...