学步园

POJ 1077

下面的代码总是TLE。。。

1. 使用STL set

#include <cstdio><br /> #include <cstring><br /> #include <queue><br /> #include <stack><br /> #include <set><br /> using namespace std;<br /> class S<br /> {<br /> public:<br /> char c[9];<br /> int op;<br /> S* p;<br /> S(char *c1 = 0, int op = 0, S* p = 0):op(op),p(p){<br /> if(c1)<br /> {<br /> /*<br /> for(int i = 0; i < 9; i++)<br /> {<br /> c[i] = c1[i];<br /> }<br /> */<br /> memcpy(c, c1, 9);<br /> }<br /> }<br /> bool operator==(char* c1)<br /> {<br /> /*<br /> for(int i = 0; i < 9; i++)<br /> {<br /> if (c[i] != c1[i])<br /> {<br /> return false;<br /> }<br /> }<br /> return true;<br /> */<br /> return memcmp(c, c1, 9) == 0;<br /> }<br /> /*<br /> bool operator==(S& s)<br /> {<br /> return (*this) == (s.c);<br /> }<br /> */<br /> bool operator<(const S& s) const<br /> {<br /> /*<br /> for(int i = 0; i < 9; i++)<br /> {<br /> if(c[i] < s.c[i])<br /> {<br /> return true;<br /> }<br /> else if(c[i] > s.c[i])<br /> {<br /> return false;<br /> }<br /> }<br /> return false;<br /> */<br /> return memcmp(c, s.c, 9) < 0;<br /> }<br /> };<br /> queue<S*> q;<br /> set<S> hash;<br /> S* getState(S *s, int op)<br /> {<br /> int loc = -1;<br /> for(int i = 0; i < 9; i++)<br /> {<br /> if(s->c[i] == 'x')<br /> {<br /> loc = i;<br /> break;<br /> }<br /> }<br /> int x = loc / 3;<br /> int y = loc % 3;<br /> //cout << "loc " << loc << " -> " << x << ", " << y << endl;<br /> int nx, ny;<br /> S* ns = 0;<br /> switch(op)<br /> {<br /> case 0:<br /> // u<br /> nx = x - 1;<br /> ny = y;<br /> break;<br /> case 1:<br /> // d<br /> nx = x + 1;<br /> ny = y;<br /> break;<br /> case 2:<br /> // l<br /> nx = x;<br /> ny = y - 1;<br /> break;<br /> case 3:<br /> // r<br /> nx = x;<br /> ny = y + 1;<br /> break;<br /> }<br /> if (nx >= 0 && nx <= 2 && ny >= 0 && ny <= 2)<br /> {<br /> ns = new S(s->c, op, s);<br /> // perform the operation<br /> ns->c[x * 3 + y] = ns->c[nx * 3 + ny];<br /> ns->c[nx * 3 + ny] = 'x';<br /> }<br /> return ns;<br /> }<br /> void print(S s)<br /> {<br /> for(int i = 0; i < 9; i++)<br /> {<br /> //cout << s.c[i];<br /> printf("%c", s.c[i]);<br /> }<br /> //cout << endl;<br /> printf("/n");<br /> }<br /> char OP[4] = {'u', 'd', 'l', 'r'};<br /> /*<br /> void print(int op)<br /> {<br /> switch(op)<br /> {<br /> case 0:<br /> cout << "u";<br /> break;<br /> case 1:<br /> cout << "d";<br /> break;<br /> case 2:<br /> cout << "l";<br /> break;<br /> case 3:<br /> cout << "r";<br /> break;<br /> }<br /> }<br /> */<br /> char C[9] = {'1', '2', '3', '4', '5', '6', '7', '8', 'x'};<br /> void BFS()<br /> {<br /> while(!q.empty())<br /> {<br /> S* ps = q.front();<br /> q.pop();<br /> if(*ps == C)<br /> {<br /> stack<int> st;<br /> while(ps->p)<br /> {<br /> st.push(ps->op);<br /> ps = ps->p;<br /> }<br /> while(!st.empty())<br /> {<br /> printf("%c", OP[st.top()]);<br /> st.pop();<br /> }<br /> //cout << endl;<br /> printf("/n");<br /> return;<br /> } </p> <p> for(int i = 0; i < 4; i++)<br /> {<br /> S *ns = getState(ps, i);</p> <p> if(ns && (hash.find(*ns) == hash.end()))<br /> {<br /> //print(*ns);<br /> hash.insert(*ns);<br /> q.push(ns);<br /> }<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> char c[9];<br /> for(int i = 0; i < 9; i++)<br /> {<br /> //cin >> c[i];<br /> scanf("%c ", &(c[i]));<br /> }</p> <p> S s(c, 0, 0);<br /> hash.insert(s);<br /> //cout << (*hash.find(s1)).op << endl;<br /> //cout << (hash.find(s1) != hash.end()) << endl;<br /> q.push(&s);<br /> BFS();<br /> }

2. 使用hash

#include <cstdio><br /> #include <cstring><br /> #include <queue><br /> #include <stack><br /> using namespace std;<br /> class S<br /> {<br /> public:<br /> char c[9];<br /> int op;<br /> S* p;<br /> S(char *c1 = 0, int op = 0, S* p = 0):op(op),p(p){<br /> if(c1)<br /> {<br /> memcpy(c, c1, 9);<br /> }<br /> }<br /> bool operator==(char* c1)<br /> {<br /> return memcmp(c, c1, 9) == 0;<br /> }<br /> bool operator==(S& s1)<br /> {<br /> return (*this) == s1.c;<br /> }<br /> bool operator<(const S& s) const<br /> {<br /> return memcmp(c, s.c, 9) < 0;<br /> }<br /> };<br /> void print(S s)<br /> {<br /> for(int i = 0; i < 9; i++)<br /> {<br /> printf("%c", s.c[i]);<br /> }<br /> printf("/n");<br /> }<br /> const int MAXSTATE = 1000000;<br /> const int MAXHASHSIZE = 1000003;<br /> int head[MAXHASHSIZE], next[MAXSTATE];<br /> S* st[MAXSTATE];<br /> int sno = 0;<br /> void init_lookup_table()<br /> {<br /> memset(head, 0, sizeof(head));<br /> }<br /> int hash(S& s)<br /> {<br /> int v = 0;<br /> for(int i = 0; i < 9; i++)<br /> v = v * 10 + s.c[i];<br /> return v % MAXHASHSIZE;<br /> }<br /> int try_to_insert(S *s)<br /> {<br /> //printf("trying insert %dth state : ", s);<br /> //print(*st[s]);<br /> int h = hash(*s);<br /> int u = head[h];<br /> while(u) {<br /> if((*st[u]) == *s)<br /> return 0;<br /> u = next[u];<br /> }<br /> next[sno] = head[h];<br /> head[h] = sno;<br /> st[sno++] = s;<br /> return 1;<br /> }<br /> queue<S*> q;<br /> S* getState(S *s, int op)<br /> {<br /> int loc = -1;<br /> for(int i = 0; i < 9; i++)<br /> {<br /> if(s->c[i] == '0')<br /> {<br /> loc = i;<br /> break;<br /> }<br /> }<br /> int x = loc / 3;<br /> int y = loc % 3;<br /> int nx, ny;<br /> S* ns = 0;<br /> switch(op)<br /> {<br /> case 0:<br /> // u<br /> nx = x - 1;<br /> ny = y;<br /> break;<br /> case 1:<br /> // d<br /> nx = x + 1;<br /> ny = y;<br /> break;<br /> case 2:<br /> // l<br /> nx = x;<br /> ny = y - 1;<br /> break;<br /> case 3:<br /> // r<br /> nx = x;<br /> ny = y + 1;<br /> break;<br /> }<br /> if (nx >= 0 && nx <= 2 && ny >= 0 && ny <= 2)<br /> {<br /> ns = new S(s->c, op, s);<br /> // perform the operation<br /> ns->c[x * 3 + y] = ns->c[nx * 3 + ny];<br /> ns->c[nx * 3 + ny] = '0';<br /> }<br /> return ns;<br /> }<br /> char OP[4] = {'u', 'd', 'l', 'r'};<br /> char C[9] = {'1', '2', '3', '4', '5', '6', '7', '8', '0'};<br /> void BFS()<br /> {<br /> while(!q.empty())<br /> {<br /> S* ps = q.front();<br /> q.pop();<br /> if(*ps == C)<br /> {<br /> stack<int> st;<br /> while(ps->p)<br /> {<br /> st.push(ps->op);<br /> ps = ps->p;<br /> }<br /> while(!st.empty())<br /> {<br /> printf("%c", OP[st.top()]);<br /> st.pop();<br /> }<br /> printf("/n");<br /> return;<br /> } </p> <p> for(int i = 0; i < 4; i++)<br /> {<br /> S *ns = getState(ps, i);</p> <p> if(ns)<br /> {<br /> if(try_to_insert(ns))<br /> {<br /> q.push(ns);<br /> }<br /> }<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> char c[9];<br /> for(int i = 0; i < 9; i++)<br /> {<br /> scanf("%c ", &(c[i]));<br /> if(c[i] == 'x')<br /> {<br /> c[i] = '0';<br /> }<br /> }</p> <p> S s(c, 0, 0);<br /> st[sno++] = &s;<br /> q.push(&s);<br /> BFS();<br /> }

测试结果：

/home/a/j/nomad2:cat input<br /> 8 6 7 2 5 4 3 x 1<br /> /home/a/j/nomad2:time cat input |./a.out<br /> uulddrruuldldrruuldldrruullddrr<br /> real 0m0.284s<br /> user 0m0.239s<br /> sys 0m0.034s

注：网上的一个hash的ac代码

#include<iostream><br /> #include<string><br /> #include<cstdlib><br /> #include<cstring><br /> #include<cstdio><br /> #include<set><br /> #include<algorithm><br /> using namespace std;<br /> const int MAXSTATE=1000000;<br /> const int MAXHASHSIZE=1000003; //定义哈希表大小<br /> typedef int state[9]; //定义"状态"类型<br /> state st[MAXSTATE],goal={1,2,3,4,5,6,7,8,0};<br /> int head[MAXHASHSIZE];<br /> int next[MAXSTATE];<br /> int dir[MAXSTATE];<br /> int p[MAXSTATE][2]; //p[s][0]存放父亲节点,p[s][1]存放移动方向<br /> int dx[4]={-1,1,0,0};<br /> int dy[4]={0,0,-1,1};<br /> char name[4]={'u','d','l','r'};<br /> void Init() //初始化哈希表表头<br /> {<br /> memset(head,0,sizeof(head));<br /> }<br /> int Hash(state & s) //哈希函数<br /> {<br /> int i,v=0;<br /> for(i=0;i<9;i++)<br /> v=v*10+s[i];<br /> return v%MAXHASHSIZE;<br /> }<br /> int Hash_Search(int s) //判重,即判断状态s是否已近拓展过<br /> {<br /> int h,u;<br /> h=Hash(st[s]);<br /> u=head[h]; //从表头开始查找<br /> while(u)<br /> {<br /> if(memcmp(st[u],st[s],sizeof(st[s]))==0) //状态st[s]已经存在<br /> return 0;<br /> u=next[u]; //否则继续查找<br /> }<br /> next[s]=head[h]; //插入到链表中<br /> head[h]=s;<br /> return 1;<br /> }<br /> int BFS()<br /> {<br /> int x,y,z,d,newx,newy,newz,front,rear;<br /> Init();<br /> front=1;<br /> rear=2;<br /> p[front][0]=-1;<br /> while(front<rear)<br /> {<br /> state & s=st[front]; //用引用简化代码<br /> if(memcmp(goal,s,sizeof(s))==0) //找到目标状态,成功返回<br /> return front;<br /> for(z=0;z<9;z++) //找0的位置,将输入中的'x'用0来表示<br /> if(s[z]==0)<br /> break;<br /> x=z/3;<br /> y=z%3;<br /> for(d=0;d<4;d++)<br /> {<br /> newx=x+dx[d];<br /> newy=y+dy[d];<br /> if(newx>=0&&newx<3&&newy>=0&&newy<3) //移动不超出范围<br /> {<br /> newz=3*newx+newy;<br /> state & t=st[rear];<br /> memcpy(&t,&s,sizeof(s)); //扩展新节点<br /> t[newz]=s[z];<br /> t[z]=s[newz];<br /> p[rear][0]=front; //存储父亲节点<br /> p[rear][1]=d; //存储该步移动方向<br /> if(Hash_Search(rear)) //如果成功插入查找表,修改队尾指针<br /> rear++;<br /> }<br /> }<br /> front++; //扩展完毕再修改队首指针<br /> }<br /> return 0; //移动失败<br /> }<br /> void Print_Path(int t) //打印移动路线<br /> {<br /> int i=0;<br /> while(p[t][0]!=-1)<br /> {<br /> dir[i++]=p[t][1];<br /> t=p[t][0];<br /> }<br /> while(i--)<br /> printf("%c",name[dir[i]]);<br /> printf("/n");<br /> }<br /> int main()<br /> {<br /> int i,ans,len,j;<br /> char ss[30];<br /> while(gets(ss)!=NULL)<br /> {<br /> len=strlen(ss);j=0;<br /> for(i=0;i<len;i++)<br /> if(ss[i]!=' ')<br /> {<br /> if(ss[i]!='x') //将'x'用0代替<br /> st[1][j++]=ss[i]-'0';<br /> else<br /> st[1][j++]=0;<br /> }<br /> ans=BFS();<br /> if(ans>1)<br /> Print_Path(ans);<br /> else //此时不存在移动方案<br /> printf("impossibile/n");<br /> }<br /> return 0;<br /> }<br />