其实我已无力吐槽了

只是一次简单的练习,抱着“复习一下”的态度做做
然后一直WA
一直WA
换了各种版本的hash函数无果
调试超过四个小时
一直WA。。。。。让我对未来充满的无力感
然后。。。。。。
发现。。。。。。。。。。
TMD有多组数据。。。。。。测试数据你说明一下可不可以啊
5555555.。。。。。。。
注:此题只是基础练习,所以不是poj和hdu上的八数码,此题只要求输出步数
如果要改成poj上的
只需要添加一个pre数组储存步骤即可

教训:看题看题。用stl简化操作

我以后会补齐用A*和BFS双向的代码。

 C
 
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156
 #include "StdAfx.h"#include 
#include
#include
#include
#include
#include
using namespace std;int f[] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320,362880}; // 阶乘表bool used[362881];int step[362881]; typedef char State[3][3];struct node{ char x,y; int val; State state; node(){ }; node (char xx,char yy,int v,State s) { x=xx;y=yy; val=v; for (int i=0;i<3;i++) for (int j=0;j<3;j++) state[i][j]=s[i][j]; }};  int hashs(State ss){ int i,j,cnt,res=0,jac=1; int s[10];for (int i=0;i<3;i++) for (int j=0;j<3;j++) s[i*3+j]=ss[i][j]; for(i=1;i<9;++i) { cnt=0; for(j=0;j
s[i]) ++cnt; res+=cnt*f[i]; } return res; }  void change(char &a,char &b){ int q=b; b=a;a=q;} queue
q;int main(){ node a,b; int vv; char c[10]; for (int i=0;i<3;i++) for (int j=0;j<3;j++) { b.state[i][j]=i*3+j+1; } vv=hashs(b.state); b.val=0; b.x=2;b.y=2; memset(used,0,sizeof(used)); used[hashs(b.state)]=true; q.push(b); node t,st; char x,y;  while (!q.empty()) { t=q.front(); q.pop(); x=t.x;y=t.y; if (x>0) {   st=t; change(st.state[x-1][y],st.state[x][y]); st.x=x-1; st.val+=1;  if (! used[hashs(st.state)]) { used[hashs(st.state)]=true; step[hashs(st.state)]=st.val; q.push(node(st.x,st.y,st.val,st.state)); } }  if (x<2) { st=t; change(st.state[t.x+1][t.y],st.state[t.x][t.y]); st.x+=1; st.val+=1; if (! used[hashs(st.state)]) { used[hashs(st.state)]=true; step[hashs(st.state)]=st.val; q.push(node(st.x,st.y,st.val,st.state)); } }  if (y>0) { st=t; change(st.state[t.x][t.y-1],st.state[t.x][t.y]); st.y-=1; st.val+=1; if (! used[hashs(st.state)]) { used[hashs(st.state)]=true; step[hashs(st.state)]=st.val; q.push(node(st.x,st.y,st.val,st.state)); } }  if (y<2) { st=t; change(st.state[t.x][t.y+1],st.state[t.x][t.y]); st.y+=1; st.val+=1; if (! used[hashs(st.state)]) { used[hashs(st.state)]=true; step[hashs(st.state)]=st.val; q.push(node(st.x,st.y,st.val,st.state)); } }  } while (1) { for (int i=0;i<3;i++) for (int j=0;j<3;j++) { if(scanf("%s", c) != 1) return 1; else { if(c[0] >= '1' && c[0] <= '8') a.state[i][j] = c[0] - '0'; else { a.state[i][j]=9; a.x=i;a.y=j; } } }  if (used[hashs(a.state)]) ("%d\n",step[hashs(a.state)]); else ("unsolvable\n"); } return 0;}