题解：AT_abc361_d [ABC361D] Go Stone Puzzle
wbh20090611 · · 题解
这道题是一道好题啊！
以下是本蒟蒻的做法：
首先，我们可以很快的想到可以使用状态压缩来实现操作，然后使用广度优先搜索或者动态规划来求解。
本蒟蒻想不到怎么用 BFS 于是用了状压 DP。
首先进行输入加状压：
string s, ll;
int n, a, b, c;
cin >> n >> s >> ll;
p = n;
for(int i = 0; i < n; i++)
{
a += (s[i] == 'W');
b += (s[i] == 'B');
if (s[i] == 'W')
x |= (1 << i);//状态压缩（'W'为1, 'B'为0）
//记录初始状态
a -= (ll[i] == 'W');
b -= (ll[i] == 'B');
if (ll[i] == 'W')
y |= (1 << i), c++;//状态压缩（'W'为1, 'B'为0）
//记录最终状态
}//c用于记录一共有多少个'W'
//a和b分别记录
if (a != 0 || b != 0)//如果'W'的个数不相同就不可能
{
cout << -1;
return 0;
}需要注意的是：先不用管 . 的表示方法，后面会提到。
预处理可能出现的状态，用动态数组存储：
1. 声明函数 check
int check(int m) //数一个数的二进制中有多少个1
{
int cnt = 0;
while(m > 0)
{
m -= (m & -m);
cnt++;
}
return cnt;
} //可以作为模板主函数：
vector <int> w;
for (int j = 0; j <= (1 << (n + 2)) - 1; j++)
{
//c用于记录一共有多少个'W'
if (check(j) == c) //当1的个数为c时成立
w.push_back(j); //计入动态数组
}动态规划：
//开始 DP
memset(dp, 0x3f3f3f3f, sizeof dp);
//把每个数变成 inf
memset(l, -1, sizeof l);
//l用于记录 dp的初值
//dp[i][j]表示空位在 i和 i+1的位置上，当前状态为 j
dp[p][x] = 0;//初始值为 0
r = true;
while((dp[p][y] == 0x3f3f3f3f || dp[p][y] != o) && (r)) //如果没有更改，就退出
{
r = false;
o = dp[p][y];
for (auto j : w) //枚举可能的状态
{
for (int i = 0; i < n + 1; i++) //枚举第一个空位的位置
{
//如果dp[i][j]和初值相同，就不必进行下一步
if(dp[i][j] >= dp[p][y] || dp[i][j] == l[i][j])
continue;
l[i][j] = dp[i][j];//更新初值
for (int z = 0, d, e, f, u, g; z < n + 1; z++) //枚举交换位的位置
{
if(z == i || z == i + 1 || z == i - 1) //如果是空位，跳过
continue;
u = j;
//记录位置并使用位运算把该位移到正确位置
if (i < z)
{
d = ((j & (1 << z)) >> (z - i));
e = ((j & (1 << i)) << (z - i));
f = ((j & (1 << (z + 1))) >> (z - i));
g = ((j & (1 << (i + 1))) << (z - i))；
}
else//由于在 <<或 >>运算中，不存在负数，因此：
{
d = ((j & (1 << z)) << (i - z));
e = ((j & (1 << i)) >> (i - z));
f = ((j & (1 << (z + 1))) << (i - z));
g = ((j & (1 << (i + 1))) >> (i - z));
}
if (j & (1 << z)) //删除该位
u -= (1 << z);
u |= e; //改变该位
//以下同理
if (j & (1 << i))
u -= (1 << i);
u |= d;
if (j & (1 << (z + 1)))
u -= (1 << (z + 1));
u |= g;
if (j & (1 << (i + 1)))
u -= (1 << (i + 1));
u |= f;
dp[z][u] = min(dp[i][j] + 1, dp[z][u]); //dp递推式
r = true;//标记更改过了
}
}
}
}
//依题意输出
if (dp[p][y] < 0x3f3f3f3f)cout << dp[p][y];
else cout << -1;最后附上详细代码：
#include <bits/stdc++.h>
using namespace std;
vector <int> w;
int n, ans = INT_MAX;
int x, y, a, b, p, dp[21][100010], l[21][100010], c, o;
int check(int m)//数一个数的二进制中有多少个1
{
int cnt = 0;
while(m > 0)
{
m -= (m & -m);
cnt++;
}
return cnt;
}//可以作为模板，时间复杂度O(log(n))
string s, ll;
bool r;
int main()
{
cin >> n >> s >> ll;
p = n;
for(int i = 0; i < n; i++)
{
a += (s[i] == 'W');
b += (s[i] == 'B');
if (s[i] == 'W')
x |= (1 << i);//状态压缩（'W'为 1, 'B'为 0）
//记录初始状态
a -= (ll[i] == 'W');
b -= (ll[i] == 'B');
if (ll[i] == 'W')
y |= (1 << i), c++;//状态压缩（'W'为 1, 'B'为 0）
//记录最终状态
}
//c用于记录一共有多少个'W'
if (a != 0 || b != 0)//如果'W'的个数不相同就不可能
{
cout << -1;
return 0;
}
for (int j = 0; j <= (1 << (n + 2)) - 1; j++)
{
//c用于记录一共有多少个'W'
if (check(j) == c) //当 1的个数为 c时成立
w.push_back(j); //计入动态数组
}
//开始 DP
memset(dp, 0x3f3f3f3f, sizeof dp);
//把每个数变成 inf
memset(l, -1, sizeof l);
//l用于记录 dp的初值
//dp[i][j]表示空位在 i和 i+1的位置上，当前状态为 j
dp[p][x] = 0;//初始值为 0
r = true;
while((dp[p][y] == 0x3f3f3f3f || dp[p][y] != o) && (r)) //如果没有更改，就退出
{
r = false;
o = dp[p][y];
for (auto j : w) //枚举可能的状态
{
for (int i = 0; i < n + 1; i++) //枚举第一个空位的位置
{
//如果dp[i][j]和初值相同，就不必进行下一步
if(dp[i][j] >= dp[p][y] || dp[i][j] == l[i][j])
continue;
l[i][j] = dp[i][j];//更新初值
for (int z = 0, d, e, f, u, g; z < n + 1; z++) //枚举交换位的位置
{
if(z == i || z == i + 1 || z == i - 1) //如果是空位，跳过
continue;
u = j;
//记录位置并使用位运算把该位移到正确位置
if (i < z)
{
d = ((j & (1 << z)) >> (z - i));
e = ((j & (1 << i)) << (z - i));
f = ((j & (1 << (z + 1))) >> (z - i));
g = ((j & (1 << (i + 1))) << (z - i));
}
else//由于在 <<或 >>运算中，不存在负数，因此：
{
d = ((j & (1 << z)) << (i - z));
e = ((j & (1 << i)) >> (i - z));
f = ((j & (1 << (z + 1))) << (i - z));
g = ((j & (1 << (i + 1))) >> (i - z));
}
if (j & (1 << z)) //删除该位
u -= (1 << z);
u |= e; //改变该位
//以下同理
if (j & (1 << i))
u -= (1 << i);
u |= d;
if (j & (1 << (z + 1)))
u -= (1 << (z + 1));
u |= g;
if (j & (1 << (i + 1)))
u -= (1 << (i + 1));
u |= f;
dp[z][u] = min(dp[i][j] + 1, dp[z][u]); //dp递推式
r = true;//标记更改过了
}
}
}
}
//依题意输出
if (dp[p][y] < 0x3f3f3f3f)cout << dp[p][y];
else cout << -1;
}