萌新80pts求调!!!十万火急
查看原帖
萌新80pts求调!!!十万火急
697898
b1tset楼主2023/3/4 12:58
#include <bits/stdc++.h>
using namespace std;

struct node
{
	int x, y, step;
};

int n, m, fx, fy, sx, sy;
bool vis[5001][5001], arrive[5001][5001];
char ch[5001][5001];
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

void init()
{
    int nx[10] = {0, -1, -1, -1, 0, 0, 1, 1, 1};
    int ny[10] = {0, -1, 0, 1, -1, 1, -1, 0, 1};
    
    arrive[fx][fy] = 1;
    for (int i = 1; i <= 8; i++)
    {
        int a = fx, b = fy;
        while (ch[a][b] != 'X' && a > 0 && b > 0 && a <= n && b <= m)
        {
        	arrive[a][b] = 1;
            a += nx[i], b += ny[i];
        }
    }
}

void bfs()
{
    queue<node> q;
    q.push({sx, sy, 0});
    vis[sx][sy] = 1;
    int x, y, s;
    
    while (q.size())
    {
        x = q.front().x, y = q.front().y, s = q.front().step;
        q.pop();
        
        if (arrive[x][y])
        {
            printf("%d\n", s);
            return ;
        }
        
        int kx, ky;
        for (int i = 1; i <= 4; i++)
        {
            kx = x + dx[i], ky = y + dy[i];
            if (kx > 0 && ky > 0 && kx < n && ky < m && !vis[kx][ky] && ch[kx][ky] != 'X')
            {
                q.push({kx, ky, s + 1});
                vis[kx][ky] = 1;
            }
        }
    }
    printf("Poor Harry\n");
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> ch[i][j];
            
    while (true)
    {
        scanf("%d %d %d %d", &fx, &fy, &sx, &sy);
        if (fx == 0 && fy == 0 && sx == 0 && sy == 0) break;
        memset(vis, 0, sizeof(vis));
        memset(arrive, 0, sizeof(arrive));
        init();
        bfs();
    }
    return 0;
}
2023/3/4 12:58
加载中...