P2298 70分找不到原因#2#4#10wa
查看原帖
P2298 70分找不到原因#2#4#10wa
638882
qiuqiuyaq楼主2023/3/4 21:22
#include <iostream>
#include <cstring>

using namespace std;
const int N =2010;
int n,m;
char a[N][N];

bool st[N][N];
typedef pair<int,int> PII;
PII q[N*N];
int dis[N][N];
int x1,y1,x2,y2;

int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int bfs()
{
    int hh = 0,tt =0;
    st[x1][y1] = true;
    q[0] ={x1,y1};
    
    while(hh<= tt)
    {
        auto t = q[hh++];
        if(t.first == x2 && t.second == y2) return dis[x2][y2];
        for(int i = 0;i < 4;i++)
        {
            int u1 = t.first + dx[i];
            int u2 = t.second + dy[i];
            if(u1 < 0 || u1 > n || u2 < 0 || u2 > m) continue;
            if(st[u1][u2]) continue;
            if(a[u1][u2] == '#') continue;
            dis[u1][u2] = dis[t.first][t.second] + 1;
            st[u1][u2] = true;
            q[++tt] = {u1,u2};
        }
    }
    printf("No Way!");
}


int main()
{
    cin >> n >> m;
    for(int i = 0;i <  n;i++ )
    {
        for(int j = 0;j < m;j++ )
        {cin >> a[i][j];
        if(a[i][j] == 'm') x1 = i,y1=j;
        if(a[i][j] == 'd') x2 = i,y2 =j;
        }
    }
 cout << bfs();
    
    
}
2023/3/4 21:22
加载中...