抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

洛谷P1225 黑白棋游戏

题意简述

求从一个 $4\times4$ 的方阵变成另一个 $4\times4$ 的方阵最少需要的步数以及步骤。
(棋子只能与相邻的棋子交换)

输入:

  • 两个 $4\times4$ 的方阵,只包含8个0和8个1。

输出:

  • 最少需要的步数。
  • 操作的每一步,格式 $abcd$,表示将棋子从 $(a,b)$ 移动到 $(c,d)$。

题目分析

这道题使用bfs。

搜索时注意交换 $(a,b)$ 和 $(a+1,b)$ 与 交换 $(a+1,b)$ 和 $(a,b)$ 是一样的效果,当枚举到 $(a+1,b)$ 时再去与 $(a,b)$ 交换就没有意义了,因为先枚举 $(a,b)$,如果能交换已经交换过了。$(a,b)$ 与 $(a,b+1)$ 也是同样的道理,所以我们可以得出结论,对于每个 $(a,b)$ ,我们搜索时仅需与右边的和下面的进行交换。交换两个相同的数也没有意义,所以可以进行判断来省略。

因为棋盘只包含0和1,且只有16位,所以可以压缩成二进制方便储存。

"样例"
比如说样例,将输入的两个方阵记为 $a$ 和 $b$,则 $a$ 可以压缩成 $1111000011100010$ 即 $61666$。

"样例-二进制"

我们可以通过 a & (1<<i) 来取得从左往右第 $i$ 位的值,则它右边的值为 a & (1<<(i-1)),下面的值为 a & (1<<(i-4))
""
""

为了记录操作,我们还需要知道第 $i$ 位在原本的方阵中对应的坐标,它的纵坐标就是 $\lfloor i\div4 \rfloor$,横坐标即为 $i\mod4$。

由于要被交换的两位必定是一个0一个1,所以交换两位可以将这两位异或1

详情请见代码:

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
struct record //用于记录步骤
{
int x1;
int y1;
int x2;
int y2;
};
struct status //每一个状态
{
int num; //方阵的二进制形式
int t; //需要的次数
vector<record> rec; //记录步骤
};
status a, b; //初始状态和目标状态
queue<status> q; //用于bfs
bool vis[66666]; //记录某个方阵是否被搜过
void bfs()
{
q.push(a);
while (!q.empty())
{
status tmp = q.front();
q.pop();
if (vis[tmp.num]) //如果搜到过那么就肯定不是最优解
{
continue;
}
vis[tmp.num] = 1;
if (tmp.num == b.num) //如果与目标相同就输出
{
cout << tmp.t << endl;
for (vector<record>::iterator it = tmp.rec.begin(); it != tmp.rec.end(); ++it)
{
cout << (it->x1) << (it->y1) << (it->x2) << (it->y2) << endl;
}
return;
}
for (int i = 15; i >= 0; --i) //枚举方阵每一位
{
/**
* 15-i表示现在是方阵二进制的哪一位(从左到右)
* (15-i) / 4 即 (15-i) >> 2 表示相当于原来的第几行
* (15-i) % 4 即 (15-i) - (y << 2) 表示相当于原来的第几列
*/
int y = (15 - i) >> 2;
int x = (15 - i) - (y << 2);

/*tmp.num & (1<<i) 表示当前方阵第i位,这里用aaa储存方便使用*/
int aaa = 1 << i;

status bbb; //临时储存下一个状态
bbb.t = tmp.t + 1;
bbb.rec = tmp.rec;

/**
* 左右交换
* 限制 x<3 防止出界
* 如果第i位与第i+1位相等就不用交换了
* 第i+1位在10进制里对应的值就是第i位的值的一半
* 因为这里的x和y是从0开始的,所以记录时要加一
*/
bbb.num = tmp.num ^ aaa ^ (aaa >> 1);
if (x < 3 and (tmp.num & aaa) ^ (tmp.num & (aaa >> 1)))
{
bbb.rec.push_back((record){y + 1, x + 1, y + 1, x + 2});
q.push(bbb);
bbb.rec.pop_back();
}

/**
* 上下交换
* 同上,不过这次是与下面的交换,需要右移一行即4位
*/
bbb.num = tmp.num ^ aaa ^ (aaa >> 4);
if (y < 3 and (tmp.num & aaa) ^ (tmp.num & (aaa >> 4)))
{
bbb.rec.push_back((record){y + 1, x + 1, y + 2, x + 1});
q.push(bbb);
bbb.rec.pop_back();
}
}
}
}
int main()
{
char ch;

/*将读入的方阵变成二进制的形式并用int保存*/
for (int i = 15; i >= 0; --i)
{
cin >> ch;
a.num += (ch - '0') * (1 << i);
}
for (int i = 15; i >= 0; --i)
{
cin >> ch;
b.num += (ch - '0') * (1 << i);
}

/*特判,如果一开始就相同那就不需要搜索了*/
if (a.num == b.num)
{
cout << 0;
return 0;
}

bfs();
return 0;
}