20分求调(玄一关)
查看原帖
20分求调(玄一关)
933264
cyLLxGP70ytRvxZTZs3f楼主2024/7/24 13:19
#include <iostream>
#include <queue>
using namespace std;
char mp[305][305];
bool vis[305][305];
int n, m, stx, sty;
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
struct node
{
    int x, y, step;
};
void find(int &x, int &y)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (mp[i][j] == mp[x][y] && !(x == i || y == j))
                x = i, y = j;
        }
    }
    return;
}
bool check(int x, int y)
{
    return x > 0 && x <= n && y > 0 && y <= m && !vis[x][y] && mp[x][y] != '#';
}
int bfs(int stx, int sty)
{
    queue<node> q;
    q.push(node{stx, sty, 0});
    vis[stx][sty] = 1;
    while (!q.empty())
    {
        node t = q.front();
        q.pop();
        if (mp[t.x][t.y] == '=')
            return t.step;
        if (mp[t.x][t.y] >= 'A' && mp[t.x][t.y] <= 'Z')
            find(t.x, t.y);
        for (int i = 0; i < 4; i++)
        {
            int dx = t.x + dir[i][0];
            int dy = t.y + dir[i][1];
            if (check(dx, dy))
            {
                vis[dx][dy] = 1;
                q.push(node{dx, dy, t.step + 1});
            }
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> mp[i][j];
            if (mp[i][j] == '@')
            {
                stx = i;
                sty = j;
            }
        }
    }
    cout << bfs(stx, sty) << '\n';
    return 0;
}

样例死都过不了 a了5,8,12

2024/7/24 13:19
加载中...