hdu1043多组数据
poj1077单组数据
1、对于空间的处理
按常规方法，标志位序列vis的大小需要876543210位，空间非常大，所以我们考虑将int转化为char 类型储存(32位机int占4字节 char 占1字节)。
又考虑，如果转化为九进制，876543210(9)-->381367044(10),进一步优化空间。
可是像111111111，333333333这样的房间，根本没有被用到，却仍然占用空间，我们考虑对空间进行进一步优化。
情况个数共为9！个-->362880将标志位序列优化至此。
将每一种情况%mod以达到哈希目的，通过邻接表实现。
2、判断解的存在
设f(x)(x!=0)代表x之前小于x的数的个数，g(x)代表f(x)之和,g(x)的奇偶性决定了问题是否有解
若两状态奇偶性不同，则无法相互转化。
a、单向广搜版本
#include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #define maxn 362882 #define ll long long using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; char s[10] = {'u','d','l','r'}; int tcnt,hcnt; const int mod = 23333; int head[mod+5]; struct Table { int pos,dir,pre; char a[10]; }tb[maxn]; struct Hash { char a[10]; int next; }htb[maxn]; queue<int>q; int build_table(int dir,int pos,int last) { ++tcnt; tb[tcnt].pos = pos; tb[tcnt].dir = dir; strcpy(tb[tcnt].a,tb[last].a); tb[tcnt].pre = last; return tcnt; } inline bool check(char *a)//判断是否达到目标状态 { for(int i = 0; i < 8; i ++) if(a[i] != '0' + i + 1) return false; return true; } inline bool valid(int x,int y)//判断出界 { return 0 <= x && x <= 2 && 0 <= y && y <= 2; } inline bool ok(int a,int b)//防止回到父亲位置 { if(a > b) swap(a,b); if(a == 0 && b == 1) return false; if(a == 2 && b == 3) return false; return true; } void output(int id)//递归输出答案 { if(!id) return; output(tb[id].pre); putchar(s[tb[id].dir]); } int change(char *a)//储存哈希值 { int ret(0); for(int i = 0; i < 8; i ++) ret = (ret<<1) + (ret <<3) + a[i]-'0'; return ret%mod; } bool available(int id)//判断解的存在性 { char *a = tb[id].a; int tot(0); for(int i = 1; i < 9; i ++){ if(a[i] == '0')continue; for(int j = 0 ; j < i ; j ++) if(a[j] < a[i]&& a[j]!='0') tot ++; } return (tot%2)^1; } void hash_insert(char *a)//添加状态 { int hash = change(a);hcnt ++; strcpy(htb[hcnt].a,a); htb[hcnt].next = head[hash]; head[hash] = hcnt; } bool issame(char *a,char *b)判断是否出现过，用于防止转圈之类的重复路径 { for(int i = 0 ; i < 9; i ++) if(a[i]!=b[i]) return false; return true; } bool query(char *a)//通过邻接表实现查询 { int hash = change(a); for(int i = head[hash]; i ; i = htb[i].next) if(issame(a,htb[i].a)) return true; return false; } bool bfs() { int pos,x,y,las,k,xx,yy,tar,idd; hash_insert(tb[0].a); q.push(0); while(!q.empty()) { int id = q.front();q.pop(); Table *p = &tb[id];//指针写法 if(check(p->a))//判断是否达到目标 { output(id); return true; } pos = p -> pos;x = pos/3,y = pos%3; las = p -> dir; for(k = 0; k < 4; k ++) { xx = x + dx[k]; yy = y + dy[k]; tar = xx*3 + yy; if(!valid(xx,yy)|| !ok(las,k)) continue;//ok函数是防止走回父亲 swap(p->a[pos],p->a[tar]);//改变0的位置 if(query(p->a)){ swap(p->a[pos],p->a[tar]); continue; }//该情况出现过 idd = build_table(k,tar,id); hash_insert(p->a);//将新状态存入hash表中 q.push(idd); swap(p->a[pos],p->a[tar]); } } return false; } int main() { char str[3];tb[0].dir = 4; for(int i = 0; i < 9; i ++){ scanf("%s",str); if(str[0] == 'x'){ tb[0].pos = i; tb[0].a[i] = '0'; continue; } tb[0].a[i] = str[0]; } if( !available(0) || !bfs()) printf("unsolvable"); }
有很多地方可以压缩减小代码量，在下面的dbfs中操作
b、dbfs版本
dbfs需要修改的地方是query，当找到相同状态时我们返回当前位置序号，如果该序号在另一个队列中那么目标状态被找到，output答案
现在解释output部分
从初始状态走向目标状态时，当我们找到交点，需要递归回去从起点输出路径；从目标状态走向起始状态时，当交点出现，直接按顺序输出路径即可。
同样的，交点的走向在两种不同情况时是相反的。
(和bfs一样的部分我就不解释了)
#include<cstdio> #include<cstring> #include<algorithm> #include<map> #include<queue> #define maxn 362882 #define ll long long using namespace std; int dx[4] = {-1,1,0,0}; int dy[4] = {0,0,-1,1}; char s1[10] = {'u','d','l','r'}; char s2[10] = {'d','u','r','l'}; int hcnt; const int mod = 23333; int head[mod+5]; int vis[2][maxn],inque[2][maxn]; struct Hash//将hash和table写在一起(其实原本就可以写在一起可是我不想改bfs的代码了...) { char a[10]; int pos,dir,pre; int next; }htb[maxn]; queue<int>q[2]; inline bool valid(int x,int y) { return 0 <= x && x <= 2 && 0 <= y && y <= 2; } inline bool ok(int a,int b) { if(a > b) swap(a,b); if(a == 0 && b == 1) return false; if(a == 2 && b == 3) return false; return true; } void output1(int id)//q[0]递归反向输出答案 { if(id <= 1) return; output1(htb[id].pre); putchar(s1[htb[id].dir]); } void output2(int id)//q[1]正向输出 { if(id <= 2) return; putchar(s2[htb[id].dir]); output2(htb[id].pre); } int change(char *a) { int ret(0); for(int i = 0; i < 8; i ++) ret = (ret<<1) + (ret <<3) + a[i]-'0'; return ret%mod; } bool available(int id) { char *a = htb[id].a; int tot(0); for(int i = 1; i < 9; i ++){ if(a[i] == '0')continue; for(int j = 0 ; j < i ; j ++) if(a[j] < a[i]&& a[j]!='0') tot ++; } return (tot%2)^1; } int hash_insert(int dir,int pos,int id)//因为一个hash值对应一个hcnt，所以将bfs中的table和hash 合起来写 { int hash = change(htb[id].a);hcnt ++; strcpy(htb[hcnt].a,htb[id].a); htb[hcnt].dir = dir; htb[hcnt].pos = pos; htb[hcnt].pre = id; htb[hcnt].next = head[hash]; head[hash] = hcnt; return hcnt; } bool issame(char *a,char *b) { for(int i = 0 ; i < 9; i ++) if(a[i]!=b[i]) return false; return true; } int query(char *a)//bfs中check与query的作用在dbfs中一致，所以用query代替check { int hash = change(a); for(int i = head[hash]; i ; i = htb[i].next) if(issame(a,htb[i].a)) return i;//返回序号数 return 0; } bool bfs() { int pos,x,y,las,k,xx,yy,tar,idd;hcnt = 2; q[0].push(1); q[1].push(2); inque[0][1]=1; inque[1][2]=1; while(!q[0].empty()&&!q[1].empty()) { int num=q[0].size()>q[1].size() ; int id = q[num].front();q[num].pop(); Hash *p = &htb[id]; pos = p -> pos;x = pos/3,y = pos%3; las = p -> dir; for(k = 0; k < 4; k ++) { xx = x + dx[k]; yy = y + dy[k]; tar = xx*3 + yy; if(!valid(xx,yy)|| !ok(las,k)) continue; swap(p->a[pos],p->a[tar]); int ba; if(ba=query(p->a)) { if(vis[num^1][ba]||inque[num^1][ba])//判断状态是否在另一队中出现 { int flg=0; if(num) { swap(id,ba); flg=1;//判断交点走向 } output1(id); if(!flg)putchar(s1[k]); else putchar(s2[k]); output2(ba); return true; } swap(p->a[pos],p->a[tar]); continue; } idd = hash_insert(k,tar,id); inque[num][idd]=1; q[num].push(idd); swap(p->a[pos],p->a[tar]); } vis[num][id]=1; inque[num][id]=0; } int num=q[0].empty(); while(!q[num].empty()) { int id = q[num].front();q[num].pop(); Hash *p = &htb[id]; pos = p -> pos;x = pos/3,y = pos%3; las = p -> dir; for(k = 0; k < 4; k ++) { xx = x + dx[k]; yy = y + dy[k]; tar = xx*3 + yy; if(!valid(xx,yy)|| !ok(las,k)) continue; swap(p->a[pos],p->a[tar]); int ba; if(ba=query(p->a)) { if(vis[num^1][ba]||inque[num^1][ba]) { int flg=0; if(num) swap(id,ba),flg=1; output1(id); if(!flg)putchar(s1[k]); else putchar(s2[k]); output2(ba); return true; } swap(p->a[pos],p->a[tar]); continue; } idd = hash_insert(k,tar,id); q[num].push(idd); inque[num][idd]=1; swap(p->a[pos],p->a[tar]); } vis[num][id]=1; inque[num][id]=0; } return false; } void init() { for(int i = 1 ; i <= hcnt ; ++i) { vis[0][i]=vis[1][i]=0; inque[0][i]=inque[1][i]=0; } for(int i = 1 ; i <= mod+1 ; ++i) head[i]=0; while(!q[0].empty()) q[0].pop(); while(!q[1].empty()) q[1].pop(); } int main() { char str[3]; while(scanf("%s",str)!=EOF) { init();
htb[1].dir = 4;
htb[2].dir = 4；
htb[1].a[0]=str[0];
if(str[0] == 'x'){
htb[1].pos = 0; htb[1].a[0] = '0'; } for(int i = 1; i < 9; i ++){ scanf("%s",str); if(str[0] == 'x'){ htb[1].pos = i; htb[1].a[i] = '0'; continue; } htb[1].a[i] = str[0]; } int hash = change(htb[1].a); head[hash] = 1; for(int i = 0 ; i < 8 ; ++i) htb[2].a[i]=i+1+'0'; htb[2].a[8]='0'; hash=change(htb[2].a); head[hash]=2; htb[2].pos=8;if( !available(1) || !bfs()) printf("unsolvable"); printf(" "); } }
接下来比较dbfs与bfs的时间及空间
bfs 时间157ms 空间7836K
dbfs 时间 0ms 空间1352K
虽然程序的时间及空间会受评测机性能的影响，但是dbfs的优越性还是显而易见的。
此篇是针对上一篇dbfs入门的加深，接下来几天会更新八数码问题的idA*版本，以解决15数码问题。
(16！超过long long 范围 ，所以针对15数码，只能使用idA*算法，仍然用dbfs的话会牵扯高精度，反而增加代码的难度了)