洛谷 P1379 八数码难题 - 一次脑瘫事件

洛谷 P1379 八数码难题 - 一次脑瘫事件 - 关于广搜八数码问题一个隐秘的 Bug

注：本篇首发于作者洛谷博客，作同步处理

（主要是一开始没东西发，先转个发过的（

好吧我真不知道我能遇到这样的bug

ps：这篇不介绍广搜思路，仅吐槽单个bug.

1. 首先贴一下原题

P1379 八数码难题

题目描述

在 \(3 \times 3\) 的棋盘上，摆有八个棋子，每个棋子上标有 \(1\) 至 \(8\) 的某一数字。棋盘中留有一个空格，空格用 \(0\) 来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为 \(123804765\) ），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入格式

输入初始状态，一行九个数字，空格用 \(0\) 表示。

输出格式

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。

样例 #1

样例输入 #1
1
283104765
样例输出 #1
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\) 项，数组存得了了。至于康托展开和逆康托展开是什么，可以看看百度词条。

貌似排成一排之后还有一个特色：根据字符串存储状态，设空格当前位置为 \(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)$ 的字符，照这样就好写状态转移了。

直接开写！

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
#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;
}

诶，感觉还行，测个样例：

1
2
3
in:283104765
out:4
correct:4

噫！好！我中了！！直接交罢：

25 分。

啊？？？怎么会事呢？测错误点看看：

1
2
3
in:603712458
out:17
correct:23

嗯……改成用 set 和 char 数组试试，可能是康托展开（或者逆康托展开）或者是 string 的毛病吧。

*小改

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
112
113
114
115
116
117
#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;
}

再试试样例：

1
2
3
in:283104765
out:4
correct:4

嗯……不好说，测个之前的错误点吧：

1
2
3
in:603712458
out:17
correct:23

……好吧，看来不是康托展开（或逆康托展开）的错……

并且写的时候调试过康托展开和逆康托展开，确实没错啊…… string 也应该不会错吧……

*于是若智的我盯着代码看了整整两天都没找到 bug ，两天后：

算了，去看看讨论吧：

“你程序的tx有问题, 比如如果'0'在边界上的话, 就不能向左移了,如下例:

1 2 3 0 4 5 6 7 8

这个例子的空格就不能向左移”

原贴

！！！！！！！！！！！！！！！！！！！！！！！！

千想万想没想到这一层——存储与实际的差别：在用一维数组存储和状态转移的时候，\(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 ：

1
2
3
4
5
if(!(aim>=0&&aim<9))
	continue;    
	   //↓改成
if(!(aim>0&&aim<=9)||(z%3==1&&aim%3==0)||(z%3==0&&aim%3==1))
	continue;

顺利的过了样例和错误点：

1
2
3
4
5
6
7
in:283104765
out:4
correct:4

in:603712458
out:23
correct:23

也AC了。

3. 尾声

*去世

算法
#C++ #算法 #广搜
洛谷 P1379 八数码难题 - 一次脑瘫事件
http://fireale.xyz/20230712/bfs-eight/
作者
Fireale焰实
发布于
2023年7月12日
许可协议