题解 P2298 【Mzc和男家丁的游戏】

· · 题解

简单而典型的广搜，基础题目，不要问我为什么交了那么多次【-_-】，我太弱了。

好吧，没什么技巧，唯一要注意的是队列不要开太大，免得MLE。

真的没什么好说的。让我水一发。------

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn=2000+20;
int n,m,map[maxn][maxn],d[maxn][maxn];
int que[(maxn*maxn)][3],head,tail;
int move[20][4],tx,ty,sx,sy;
void write(int n){
    if(n>9) write(n/10);
    putchar((n % 10)+'0');
    return;
}
void init(){
    move[1][1]=1,move[1][2]=0;
    move[2][1]=-1,move[2][2]=0;
    move[3][1]=0,move[3][2]=1;
    move[4][1]=0,move[4][2]=-1;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=m+1;j++){
            map[i][j]=-1;
            d[i][j]=1234567890;
        }
    char s[maxn];
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        for(int j=0;j<m;j++){
            if(s[j]=='.') map[i][j+1]=0;
            if(s[j]=='d') map[i][j+1]=0,tx=i,ty=j+1;
            if(s[j]=='m') map[i][j+1]=0,sx=i,sy=j+1;
        }
    }
    return;
}
void tool(int x,int y,int d){
    printf("%d %d %d\n",x,y,d);
}
void bfs(){
    head=tail=0;
    d[sx][sy]=0;
    que[tail][1]=sx,que[tail][2]=sy;
    ++tail;
    while(head<tail){
        int x=que[head][1];
        int y=que[head][2];
        if(x==tx && y==ty){
            write(d[x][y]);
            return;
        }
        ++head;
        //tool(x,y,d[x][y]);
        for(int i=1;i<=4;i++){
            int px=x+move[i][1];
            int py=y+move[i][2];
            if(map[px][py]==-1) continue;
            if(d[px][py]>(d[x][y]+1)){
                d[px][py]=d[x][y]+1;
                que[tail][1]=px;
                que[tail][2]=py;
                ++tail;
            }
        }
    }
    printf("No Way!");
    return;
}
void test(){
    putchar('\n');
    printf("%d %d %d %d",sx,sy,tx,ty);
}
int main(){
    init();
    bfs();
    //test();
    return 0;
}