蒟蒻广搜写炸了
查看原帖
蒟蒻广搜写炸了
342361
Ender_beater楼主2021/9/25 16:22

广搜写炸了,帮帮蒟蒻吧。

# include <bits/stdc++.h>
using namespace std;
char a[1000][1000];
struct Node
{
    int x, y;
};

queue <Node> q;
int ans = 99999999;
int dir[5][3] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool vis[1000][1000];
int n, m;

void bfs(int dx, int dy, int csx, int csy, int cs1x, int cs1y)
{
    int sum = 0;
    Node start;
    start.x = dx;
    start.y = dy;
    q.push(start);
    while (!q.empty())
    {
        start = q.front();
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = start.x + dir[i][0];
            int ny = start.y + dir[i][1];
            Node tmp;
            tmp.x = nx;
            tmp.y = ny;
            if (a[nx][ny] != '#' && nx <= m && nx >= 1 && ny <= n && ny >= 1)
            {
                vis[nx][ny] = true;
                if (a[nx][ny] == '.' && !vis[nx][ny])
                {
                    q.push(tmp);
                    sum++;
                }
                if (a[nx][ny] == 'W')
                {
                    if (nx == csx && ny == csy)
                    {
                        sum++;
                        nx = cs1x;
                        ny = cs1y;
                        tmp.x = nx;
                        tmp.y = ny;
                        q.push(tmp);
                    }
                    if (nx == cs1x && ny == cs1y)
                    {
                        sum++;
                        nx = csx;
                        ny = csy;
                        tmp.x = nx;
                        tmp.y = ny;
                        q.push(tmp);
                    }
                }
                if (a[nx][ny] == '=')
                {
                    ans = min(ans, sum);
                    sum = 0;
                }
            }
        }
    }
}

int main()
{
    cin >> m >> n;
    int dx, dy;
    int csx, csy;
    int cs1x, cs1y;
    int k = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == '@')
            {
                dx = i;
                dy = j;
            }
            if (a[i][j] == 'W' && k == 0)
            {
                csx = i;
                csy = j;
                k = 1;
            }
            if (a[i][j] == 'W' && k == 1)
            {
                cs1x = i;
                cs1y = j;
            }
        }
    }
    bfs(dx, dy, csx, csy, cs1x, cs1y);
    cout << ans << endl;
    // system("pause");
    return 0;
}
2021/9/25 16:22
加载中...