[kuangbin带你飞]专题一 简单搜索 -N Find a

[kuangbin带你飞]专题一 简单搜索 -N Find a way

思路：两个bfs，打表

• 刚开始考虑的是碰到一个@就bfs一次，tle了
• 想到每次搜索很多重复操作，可以两次搜索用两个数组存储到达每个点的结果就好了。
• memset想设置其他数字出现了问题，注意储存结果的数组中达到不了的点需要处理。因为初始化为0时，如果达到不了时间就是0，会影响结果。

AC代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue> 
using namespace std;
int vis[210][210];
int dis[210][210][2];
char mm[210][210];
int N,M;
int mov[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

struct node{
    int x;
    int y;
    int info;
    int time;
};

bool check(node nextnode){
    if(nextnode.x<0||nextnode.y<0||nextnode.x>=N||nextnode.y>=M||mm[nextnode.x][nextnode.y]=='#'||vis[nextnode.x][nextnode.y]){
        
        return false;
    }
    return true;
}

int bfs(node st,int info){
    queue<node> Q;
    Q.push(st);
    vis[st.x][st.y] =true;
    while(!Q.empty()){
        node nownode;
        node nextnode;
        nownode = Q.front();Q.pop();
        for(int i = 0 ;i<4;i++){
            
            nextnode.x = nownode.x+mov[i][0];
            nextnode.y = nownode.y+mov[i][1];
            if(check(nextnode)){
                nextnode.time = nownode.time+1;
                vis[nextnode.x][nextnode.y] = true;
                dis[nextnode.x][nextnode.y][info] = nextnode.time;
                Q.push(nextnode);
            }
        }
        
    }
    return 0;
}

int main(){
    while(scanf("%d%d",&N,&M)!=EOF){
        node stY;
        node stM;
        stY.time = 0;
        stM.time = 0;
        int mintime=99999999;
        memset(dis,0,sizeof(dis));
        for(int i = 0 ; i < N ; i++){
            scanf("%s",mm[i]);
            for(int j = 0 ; j < M ; j++){
                if('Y' == mm[i][j]){
                    stY.x = i;
                    stY.y = j;
    
                }
                if('M' == mm[i][j]){
                    stM.x = i;
                    stM.y = j;
                }
            }
        }
        memset(vis,false,sizeof(vis));
        bfs(stY,0);
        memset(vis,false,sizeof(vis));
        bfs(stM,1);
        
        for(int i = 0 ;i<N;i++){
            for(int j = 0 ; j< M;j++){
//              cout<<"temt"<<endl;
                if('@' == mm[i][j]){
                    int timeY;
                    int timeM;
                    timeY = dis[i][j][0];
                    timeM = dis[i][j][1];
                    if(timeY!=0&&timeM!=0&&timeY+timeM<mintime){
                        mintime = timeY+timeM;
                    }
                }
            }
        }
        printf("%d\n",mintime*11);
    }
}