一次脑瘫事件 - 广搜八数码问题
fireale
2023-04-30 15:28:10
一次脑瘫事件 - 关于广搜八数码问题一个隐秘的 Bug
好吧我真不知道我能遇到这样的bug
------------
### 1. 首先贴一下[原题（P1379）](https://www.luogu.com.cn/problem/P1379)
------------
------------
## 八数码难题
### 题目描述
在 $3\times 3$ 的棋盘上，摆有八个棋子，每个棋子上标有 $1$ 至 $8$ 的某一数字。棋盘中留有一个空格，空格用 $0$ 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 $123804765$），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
### 输入格式
输入初始状态，一行九个数字，空格用 $0$ 表示。
### 输出格式
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。
### 样例 #1
#### 样例输入 #1
```
283104765
```
#### 样例输出 #1
```
4
```
### 提示
#### 样例解释
图中标有 $0$ 的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。
并且可以证明，不存在更优的策略。
------------
------------
### 2. 分析
~~一眼丁真，~~ 最少移动步数，鉴定为广搜
至于判重，声明一个9维数组vis，利用桶的思想我们执行 $if(vis[s[0]][s[1]][s[2]]...[s[8]])$ ？虽然可以 $O(1)$ 时间判重，但是 $9$ 维数组每一维都要包含 $9$ 个元素，总共 $9^9=387420489$ 项，太多了，数组开不了这么大
注意到可以把 $9$ 个数字从左到右、从上到下**排成排列数**，鉴定为康托展开，再写个逆康托展开
。这样就只有 $9!=362880$ 项，数组存得了了。至于康托展开和逆康托展开是什么，可以看看[百度百科词条](https://baike.baidu.com/item/%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80)
貌似排成一排之后还有一个**特色**：根据字符串存储状态，设空格当前位置为 $P$ ，则有：
1. 空格向上移动：空格位置减 $3$ ，即交换 $P$ 和 $P-3$ 的字符
2. 空格向左移动：空格位置减 $1$ ，即交换 $P$ 和 $P-1$ 的字符
3. 空格向右移动：空格位置加 $1$ ，即交换 $P$ 和 $P+1$ 的字符
4. 空格向下移动：空格位置加 $3$ ，即交换 $P$ 和 $P+3$ 的字符
如果设规则编号为 $k$ ，则上述四条规则可归纳为一条：**交换 $P$ 和 $P+(2*k-5)$ 的字符**，照这样就好写状态转移了
直接开写！——
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
//#include<cctype>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=362881,dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1},
fac[]={1,1,2,6,24,120,720,5040,40320,362880};
//struct ikun{
// int x,y,step;
//}q[maxn];
int n,fi,que[maxn],ti,step[maxn];
bool memo[maxn+10];
string ts,tts;
inline int Max(int a,int b){return a>b?a:b;};
void bfs(int x,int y);
int turn(string a);
string inturn(int a);
int main(){
fi=turn("123804765");
cin>>ts;
int head=0,tail=1,z;
que[1]=turn(ts),step[1]=0;
// printf("%d\n",que[1]);
// string ttt=inturn(que[1]);
// cout<<ttt;
if(que[1]==fi){
printf("0");
return 0;
}
while(tail>head){
head++,ts=inturn(que[head]);
for(int i=1;i<=4;i++){
tts=ts;
for(z=0;z<9;z++)
if(tts[z]=='0')
break;
int aim=z+2*i-5;
if(!(aim>=0&&aim<9))
continue;
swap(tts[z],tts[aim]);
ti=turn(tts);
if(!memo[ti]){
tail++,memo[ti]=true,que[tail]=ti,step[tail]=step[head]+1;
if(ti==fi){
printf("%d",step[tail]);
return 0;
}
}
}
}
printf("-1");
return 0;
}
int turn(string a){
int sum=0,cnt;
for(int i=0;i<9;i++){
cnt=0;
for(int j=i+1;j<9;j++)
if(a[j]<a[i])
cnt++;
sum+=cnt*fac[8-i];
}
return sum;
}
string inturn(int a){
string str;
int b,c,sum,num[9];
bool pl[10]={0};
for(int i=8;i>=0;i--){
b=a/fac[i],c=a-fac[i]*b,sum=0;
for(int j=0;j<=8;j++){
if(pl[j])
continue;
sum++;
if(sum==b+1)
num[8-i]=j,pl[j]=true;
}
a=c;
}
for(int i=0;i<9;i++)
str=str+(char)(num[i]+'0');
return str;
}
```
诶，感觉还行，测个样例——
```
in:283104765
out:4
correct:4
```
噫！好！我中了！！直接交罢——
### [**$25$ 分。**](https://www.luogu.com.cn/record/107949468)
啊？？？怎么会事呢？测个错误点看看——
```
in:603712458
out:17
correct:23
```
嗯……改成用 $set$ 和 $char$ 数组试试，可能是康托展开（或者逆康托展开）或者是 $string$ 的毛病吧
\*小改
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
//#include<cctype>
#include<algorithm>
#include<set>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=362881,dx[]={0,1,-1,0,0},dy[]={0,0,0,1,-1},
fac[]={1,1,2,6,24,120,720,5040,40320,362880};
int n,fi,que[maxn],ti,step[maxn];
//bool memo[maxn+10];
//string ts,tts;
int ts,tts;
set<int> memo;
inline int Max(int &a,int &b){return a>b?a:b;};
//int turn(string a);
//string inturn(int a);
int change(int aim,int &p1,int &p2);
int main(){
memo.clear();
// fi=turn("123804765");
fi=123804765;
// cin>>ts;
scanf("%d",&que[1]);
int head=0,tail=1,z;
// que[1]=turn(ts),step[1]=0;
step[1]=0;
// printf("%d\n",que[1]);
// string ttt=inturn(que[1]);
// cout<<ttt;
if(que[1]==fi){
printf("0");
return 0;
}
while(tail>head){
// head++,ts=inturn(que[head]);
head++,ts=que[head];
for(int i=1;i<=4;i++){
tts=ts;
// for(z=0;z<9;z++)
// if(tts[z]=='0')
// break;
for(z=9;z>=1;z--){
if(tts%10==0)
break;
tts/=10;
}
tts=ts;
int aim=z+2*i-5;
if(!(aim>=0&&aim<9))
continue;
// swap(tts[z],tts[aim]);
// ti=turn(tts);
ti=change(tts,z,aim);
if(!memo.count(ti)){//!memo[ti]
// tail++,memo[ti]=true,que[tail]=ti,step[tail]=step[head]+1;
tail++,memo.insert(ti),que[tail]=ti,step[tail]=step[head]+1;
if(ti==fi){
printf("%d",step[tail]);
return 0;
}
}
}
}
printf("-1");
return 0;
}
//
//int turn(string a){
// int sum=0,cnt;
// for(int i=0;i<9;i++){
// cnt=0;
// for(int j=i+1;j<9;j++)
// if(a[j]<a[i])
// cnt++;
// sum+=cnt*fac[8-i];
// }
// return sum;
//}
//
//string inturn(int a){
// string str;
// int b,c,sum,num[9];
// bool pl[10]={0};
// for(int i=8;i>=0;i--){
// b=a/fac[i],c=a-fac[i]*b,sum=0;
// for(int j=0;j<=8;j++){
// if(pl[j])
// continue;
// sum++;
// if(sum==b+1)
// num[8-i]=j,pl[j]=true;
// }
// a=c;
// }
// for(int i=0;i<9;i++)
// str=str+(char)(num[i]+'0');
// return str;
//}
int change(int n,int &p1,int &p2){
int temp[10];
for(int i=9;i>=1;i--)
temp[i]=n%10,n/=10;
temp[p1]^=temp[p2],temp[p2]^=temp[p1],temp[p1]^=temp[p2],n=0;
for(int i=1;i<=9;i++)
n=(n*10+temp[i]);
return n;
}
```
再试试样例——
```
in:283104765
out:4
correct:4
```
嗯……不好说，测个之前的错误点吧——
```
in:603712458
out:17
correct:23
```
……好吧，看来不是康托展开（或逆康托展开）的错
并且写的时候调试过康托展开和逆康托展开，确实没错啊…… $string$ 也应该不会错吧……
\*于是若智的我盯着代码看了整整两天都没找到 $bug$ ，两天后：
算了，去看看讨论吧——
```
“你程序的tx有问题, 比如如果'0'在边界上的话, 就不能向左移了,如下例:
1 2 3
0 4 5
6 7 8
这个例子的空格就不能向左移”
```
[原贴](https://www.luogu.com.cn/discuss/196975)
### **！！！！！！！！！！！！！！！！！！！！！！！！**
千想万想没想到这一层——存储与实际的差别：在用一维数组存储和状态转移的时候， $1\ 2\ 3\ 0\ 4\ 5\ 6\ 7\ 8$ 把 $3$ 和 $5$ 交换变成 $1\ 2\ 0\ 3\ 4\ 5\ 6\ 7\ 8$ 看来是显而易见符合这个精炼的公式：**交换 $P$ 和 $P+(2*k-5)$ 的字符**，但是在二维里面却是不合理的移动
于是我只用了 $2$ 分钟加一点判断就改好了困扰我两天的 $bug$ ——
```cpp
if(!(aim>=0&&aim<9))
continue;
↓改成
if(!(aim>0&&aim<=9)||(z%3==1&&aim%3==0)||(z%3==0&&aim%3==1))
continue;
```
顺利的过了样例和错误点——
```
in:283104765
out:4
correct:4
in:603712458
out:23
correct:23
```
[也AC了](https://www.luogu.com.cn/record/108020669)
------------
### 3. 尾声
\*去世