AT_abc339_d 题解

yyrwlj · 2024-02-03 22:49:00 · 题解

题意简述

棋盘上有两枚棋子，有些格子可以到达，有些不能，不能超出边界。

每次可以让两枚棋子朝相同的方向移动，若某个棋子的下一个位置不允许到达，则该棋子这次不会移动。求将两枚棋子移动到同一格

思路

考虑 bfs，因为 n \le 60，所以总状态数最多是 60^4 = 12960000，不会超时和超空间。

队列同时记录两个棋子的位置，然后记忆化一下，不走重复的状态。

然后按照题意模拟即可，如果某个棋子扩展出来的位置无法到达，那就让它保持不动就行。

Code

const int mx[4] = {0, 1, 0, -1}, my[4] = {1, 0, -1, 0};
struct Node{
    int x1, y1, x2, y2, s;
};
int main()
{
    cin >> n;
    int x1 = 0, y1, x2, _y2; 
    memset(a, '#', sizeof a);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 'P')
            {
                if (x1)
                    x2 = i, _y2 = j;
                else
                    x1 = i, y1 = j;
            }
        }
    f[x1][y1][x2][_y2] = true;
    q.push({x1, y1, x2, _y2, 0});
    while (!q.empty())
    {
        Node t = q.front();
        q.pop();
        if (t.x1 == t.x2 && t.y1 == t.y2)
        {
            printf("%d", t.s);
            return 0;
        }
        for (int i=0;i<4;i++)
        {
            int nx1 = t.x1 + mx[i], ny1 = t.y1 + my[i];
            int nx2 = t.x2 + mx[i], ny2 = t.y2 + my[i];
            if (a[nx1][ny1] == '#')
                nx1 = t.x1, ny1 = t.y1;
            if (a[nx2][ny2] == '#')
                nx2 = t.x2, ny2 = t.y2;
            if (f[nx1][ny1][nx2][ny2])
                continue;
            f[nx1][ny1][nx2][ny2] = true;
            q.push({nx1, ny1, nx2, ny2, t.s + 1});
        }
    }
    puts("-1");
    return 0;
}