首页 > 代码库 > poj 1077 + HOJ 10466 + hdu 1043 eight
poj 1077 + HOJ 10466 + hdu 1043 eight
此题我用了2种方法去做,bfs和双向 bfs 现在还在学A*,准备学会了再用A*去试试,单向bfs只过了poj,双向bfs全部都过了,具体思想就是搜索加判重,有用hash,有用康托展开,不过康托展开比较方便,因为毕竟可以一一对应,就不用判重的时候还要比较9个数了,康托展开的计算方法是:从最高位开始,在它位数前面比它小的所有数的数量再乘以它(位数-1)的阶乘,再把每一位的这个值给加起来,就是要求的。讲起来很晦涩,其实就是代表数字排列顺序的先后,比如321的康托展开 = 2×2!+ 1×1!=5是第5位,因为是从0开始数的,所以就是3!-1就是5了,312=2×2!=4 还有123 = 0,这样就可以让0-8总共9个数一一和9!一一对应起来了。
HOJ10466代码:这只用求步数就可以了不用给出路径,但是数据挺强大的,我双向BFS还用了828ms。
#include<cstdio> #include<ctype.h> #include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<stack> #include<cmath> #include<queue> #include<set> using namespace std; #define MAX 500000 #define NMAX 1000007 int cantor[9],vis[MAX],dist[MAX]; int ans; bool found; short dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1}; typedef struct status { int state[9]; }status; queue<status>q1; queue<status>q2; status st,go; void initcantor() { cantor[0] = 1; for(int i = 1; i < 9; i++) cantor[i] = cantor[i-1]*i; } void init() { ans=0; memset(dist,0,sizeof(dist)); memset(vis,0,sizeof(vis)); while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); } int gethash(status &s) { int code = 0; for(int i = 0; i < 9; i++) { int cnt = 0; for(int j = i+1; j < 9; j++) if(s.state[i] > s.state[j]) cnt++; code += cantor[8-i]*cnt; } return code; } void bfs_expend(queue<status>&q,int flag) { int ff; if(flag == 1) ff = 2; else ff = 1; status temp = q.front(); q.pop(); int z; for(z = 0; temp.state[z] != 0; z++); int x = z/3,y = z%3; int h = gethash(temp); for(int i = 0; i < 4; i++) { status t1=temp; int newx = x+dx[i],newy = y+dy[i]; if(newx>=0 && newx < 3 && newy>=0 && newy < 3) { int newz = 3*newx+newy; int k = t1.state[newz]; t1.state[z] = k; t1.state[newz] = 0; int newh = gethash(t1); if(vis[newh] == ff) { ans = dist[newh] + dist[h]+1; found = true; return; } if(vis[newh] != flag) { q.push(t1); vis[newh] = flag; dist[newh] = dist[h] + 1; } } } } void TBFS() { found = false; memset(vis,0,sizeof(vis)); vis[gethash(st)] = 1; vis[gethash(go)] = 2; q1.push(st); q2.push(go); while(!q1.empty() || !q2.empty()) { if(!q1.empty()) bfs_expend(q1,1); if(found) return; if(!q2.empty()) bfs_expend(q2,2); if(found) return; } } int main() { initcantor(); init(); int i,j; for(i = 0; i < 9; i++) scanf("%d",&st.state[i]); for(i = 0; i < 9; i++) scanf("%d",&go.state[i]); if(memcmp(st.state,go.state,sizeof(st.state)) == 0) { printf("0\n"); return 0; } TBFS(); if(!ans) printf("-1\n"); else printf("%d\n",ans); return 0; }
poj和hdu的代码
#include<cstdio> #include<ctype.h> #include<algorithm> #include<iostream> #include<cstring> #include<vector> #include<stack> #include<cmath> #include<queue> #include<set> using namespace std; #define MAX 365000 int cantor[9],vis[MAX]; int move1[MAX],move2[MAX]; int father1[MAX],father2[MAX]; int path[1000],record; bool found; short dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1}; char pos1[5] = "urdl"; char pos2[5] = "dlur"; typedef struct status { int state[9]; } status; queue<status>q1; queue<status>q2; stack<char>ss; status st,go; void initcantor() { cantor[0] = 1; for(int i = 1; i < 9; i++) cantor[i] = cantor[i-1]*i; } void init() { record=0; found = false; memset(vis,0,sizeof(vis)); while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); } int gethash(status &s) { int code = 0; for(int i = 0; i < 9; i++) { int cnt = 0; for(int j = i+1; j < 9; j++) if(s.state[i] > s.state[j]) cnt++; code += cantor[8-i]*cnt; } return code; } void bfs_expend(queue<status>&q,int flag) { int ff; if(flag == 1) ff = 2; else ff = 1; status temp = q.front(); q.pop(); int z; for(z = 0; temp.state[z] != 0; z++); int x = z/3,y = z%3; int h = gethash(temp); for(int i = 0; i < 4; i++) { status t1=temp; int newx = x+dx[i],newy = y+dy[i]; if(newx>=0 && newx < 3 && newy>=0 && newy < 3) { int newz = 3*newx+newy; int k = t1.state[newz]; t1.state[z] = k; t1.state[newz] = 0; int newh = gethash(t1); if(vis[newh] == ff) { record = newh; if(ff == 2) { move1[newh] = i; father1[newh] = h; } else { move2[newh] = i; father2[newh] = h; } found = true; return; } if(vis[newh] != flag) { if(flag == 1) { move1[newh] = i; father1[newh] = h; } else { move2[newh] = i; father2[newh] = h; } q.push(t1); vis[newh] = flag; } } } } void TBFS() { vis[gethash(st)] = 1; vis[gethash(go)] = 2; q1.push(st); q2.push(go); while(!q1.empty() || !q2.empty()) { if(!q1.empty()) bfs_expend(q1,1); if(found) return; if(!q2.empty()) bfs_expend(q2,2); if(found) return; } } void find_path(int start,int end) { int temp = record; ss.push(pos1[ move1[temp] ]); while(father1[temp] != start) { temp = father1[temp]; ss.push(pos1[ move1[temp] ]); } while(!ss.empty()) { printf("%c",ss.top()); ss.pop(); } temp = record; printf("%c",pos2[ move2[temp] ]); while(father2[temp] != end) { temp = father2[temp]; printf("%c",pos2[ move2[temp] ]); } printf("\n"); } int main() { initcantor(); int i,j; for(i = 0; i < 8; i++) go.state[i] = i+1; go.state[8] = 0; int coo=0; char temp; while(cin>>temp) { init(); if(temp == ‘x‘) st.state[0] = 0; else st.state[0] = temp-‘0‘; for(i = 1; i < 9; i++) { cin>>temp; if(temp == ‘x‘) st.state[i] = 0; else st.state[i] = temp-‘0‘; } coo=0; for(i = 1; i < 9; i++) for(j = 0; j < i; j++) { if(!st.state[i] || !st.state[j]) continue; if(st.state[i] < st.state[j]) coo++; } if(coo%2 == 1) printf("unsolvable\n"); else { TBFS(); find_path(gethash(st),gethash(go)); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。