AcWing 1103. 棋盘游戏
宋标 Lv5
  2022-08-18 02:30:53 2022-08-18 02:30    

题目

在一个 的棋盘上有 个黑棋和 个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。

移动棋子的规则是交换相邻两个棋子。

给出一个初始棋盘和一个最终棋盘，请找出一个最短的移动序列使初始棋盘变为最终棋盘。

输入格式

第一行到第四行，每行 个数字（ 或者 ），描述了初始棋盘；

接着是一个空行；

第六行到第九行，每行 个数字（ 或者 ），描述了最终棋盘。

数字 表示白棋，数字 表示黑棋。

输出格式

输出一个整数，表示最少的移动步数。数据保证有解。

输入样例:

1111
0000
1110
0010

1010
0101
1010
0101

输出样例：

4

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <queue>
#include <unordered_map>
#define N 4

using namespace std;

string start, target;

int bfs()
{
    if (start == target) return 0;

    unordered_map<string, int> map;
    queue<string> q;
    q.push(start);
    map[start] = 0;

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    while (q.size())
    {
        auto qt = q.front(); q.pop();

        for (int x = 0; x < N; ++ x) 
            for (int y = 0; y < N; ++ y)
                for (int i = 0; i < 4; ++ i)
                {
                    string t = qt;
                    int a = x + dx[i], b = y + dy[i];

                    if (a >= 0 && a < N && b >= 0 && b < N)
                    {
                        int dist = map[t];
                        swap(t[x * N + y], t[a * N + b]);
                        if (!map.count(t)) 
                        {
                            map[t] = dist + 1;
                            if (t == target) return map[t];
                            q.push(t);
                        }
                    }
                }
    }

    return 0x3f3f3f3f;
}

int main()
{
    ios::sync_with_stdio(false);

    for (int i = 0; i < N; ++ i) 
        for (int j = 0; j < N; ++ j)
        {
            char t; cin >> t; start += t;
        }

    for (int i = 0; i < N; ++ i) 
        for (int j = 0; j < N; ++ j)
        {
            char t; cin >> t; target += t;
        }

    cout << bfs() << endl;

    return 0;
}
 评论