那个网站可以做微课,wordpress案例,上海市住房和城乡建设厅官方网站,免费推广链接挺不错的题目#xff0c;很锻炼代码能力和调试能力~ 题意#xff1a;初始格子状态固定#xff0c;给你移动后格子的状态#xff0c;问最少需要多少步能到达#xff0c;如果步数大于30#xff0c;输出-1。 由于单向搜索状态太多#xff0c;搜到二十几就会爆了#xff0c…挺不错的题目很锻炼代码能力和调试能力~ 题意初始格子状态固定给你移动后格子的状态问最少需要多少步能到达如果步数大于30输出-1。 由于单向搜索状态太多搜到二十几就会爆了所以应该想到双向广搜。 对于每一个格子我只需要记录上面和前面的格子颜色因为格子左右移动前面颜色不变上面颜色变了前后移动的话只是前面和上面的颜色交换了而已不过写的太挫了。。。应该直接进制压缩一下。。。我还用了两个数来表示前面和上面的颜色下次把这些搜索题全A了后再回来重新写一下重写效果也会不错并不是题目a了这题就好了。 #include stdio.h
#include string.h#define LL __int64const int mod 100007;
struct HASH{int head[mod10], E, next[222222];int v1[222222], v2[222222], c[222222];void init() {memset(head, -1, sizeof(head));E 0;}int gethash(int x,int y) {return (((LL)x y)%modmod)%mod;}int isin(int x, int y) {int u gethash(x, y);for(int i head[u];i ! -1;i next[i]) {if(v1[i] x v2[i] y) return c[i];}return -1;}void push(int x, int y, int step) {int u gethash(x, y);v1[E] x;v2[E] y;c[E] step;next[E] head[u];head[u] E;}
}ha1, ha2;struct PP{int st1, st2;int step;PP(){}PP(int st1, int st2, int step) : st1(st1), st2(st2), step(step) {}
}cur, to, q[1000002];int dx[] {1, -1, 0, 0};
int dy[] {0, 0, 1, -1};
int a[22], b[22], d[2222];void swap(int a, int b) {int t a; a b; b t;
}void get_zt(int st1, int st2) {for(int i 9;i 1;i --) a[i] st1%10, st1 / 10;for(int i 9;i 1;i --) b[i] st2%10, st2 / 10;
}void get_xy(int st1, int st2) {st1 st2 0;for(int i 1;i 9; i) st1 st1*10a[i];for(int i 1;i 9; i) st2 st2*10b[i];
}bool judge(int go) {int ret 0;for(int i 1;i 9; i) ret ret*10a[i];return go ret;
}int getnew(int a, int b) {int vis[5], i;for(i 1;i 3; i) vis[i] 0;vis[a];vis[b];for(i 1;i 3; i) if(!vis[i]) return i;
}int min(int a, int b) {return ab?b:a;
}int bfs(int st1,int st2, int go) {ha1.init();ha1.push(st1, st2, 0);int head 0, tail 0;q[tail] PP(st1, st2, 0);int i, j, k;while(head tail) {cur q[head];st1 cur.st1, st2 cur.st2;get_zt(st1, st2);int now ;for(i 1;i 9; i) if(a[i] 4) {now i; break;}int x now/31, y now%3;if(y 0) y 3, x--;for(i 0;i 4; i) {int xx xdx[i];int yy ydy[i];if(xx 1 || xx 3 || yy 1 || yy 3) continue;int then (xx-1)*3yy;swap(a[now], a[then]);swap(b[now], b[then]);if(i 2) {swap(a[now], b[now]);if(judge(go)) {return cur.step1;}get_xy(to.st1, to.st2);to.step cur.step1;if(ha1.isin(to.st1, to.st2) -1 to.step 20) {ha1.push(to.st1, to.st2, to.step);if(to.step 20) continue;q[tail] to;}swap(a[now], b[now]);}else {a[now] getnew(a[now], b[now]);if(judge(go)) {return cur.step1;}get_xy(to.st1, to.st2);to.step cur.step1;if(ha1.isin(to.st1, to.st2) -1 to.step 20) {ha1.push(to.st1, to.st2, to.step);if(to.step 20) continue;q[tail] to;}a[now] getnew(a[now], b[now]);}swap(a[now], a[then]);swap(b[now], b[then]);}}int temp , tot 0;int N 18;for(i 0;i N; i) {temp go;for(j 9;j 1; j--)a[j] temp%10 , temp / 10;int id1 1, id2 0, sum 0;while(id1 9) {if(a[id1] 4) {sum sum*104;id1;continue;}if((1id2) i) {for(k 3;k 1; k--) if(k ! a[id1]) break;sum sum*10k;}else {for(k 1;k 3; k) if(k ! a[id1]) break;sum sum*10k;}id1, id2;}d[tot] sum;}for(i 0;i tot; i){int now ha1.isin(go, d[i]);if(now 0) return now;}int ans 1111111;for(int ii 0;ii tot;ii) {ha2.init();cur PP(go, d[ii], 0);int head 0, tail 0;q[tail] cur;int ok 0;while(head tail) {cur q[head];st1 cur.st1, st2 cur.st2;get_zt(st1, st2);int now ;for(i 1;i 9; i) if(a[i] 4) {now i; break;}int x now/31, y now%3;if(y 0) y 3, x--;for(i 0;i 4; i) {int xx xdx[i];int yy ydy[i];if(xx 1 || xx 3 || yy 1 || yy 3) continue;int then (xx-1)*3yy;swap(a[now], a[then]);swap(b[now], b[then]);if(i 2) {swap(a[now], b[now]);get_xy(to.st1, to.st2);to.step cur.step1;int temp ha1.isin(to.st1, to.st2);if(temp 0) {ok 1;ans min(ans, tempto.step);continue;}if(ha2.isin(to.st1, to.st2) -1 to.step 10) {ha2.push(to.st1, to.st2, to.step);q[tail] to;}swap(a[now], b[now]);}else {a[now] getnew(a[now], b[now]);get_xy(to.st1, to.st2);to.step cur.step1;int temp ha1.isin(to.st1, to.st2);if(temp 0) {ok 1;ans min(ans, tempto.step);continue;}if(ha2.isin(to.st1, to.st2) -1 to.step 10) {ha2.push(to.st1, to.st2, to.step);q[tail] to;}a[now] getnew(a[now], b[now]);}swap(a[now], a[then]);swap(b[now], b[then]);if(ok) break;}if(ok) break;}}if(ans 30) return -1;return ans;
}int main() {int i, x, n, m;while(scanf(%d%d, m, n) ! -1 n) {int go 0, st1 0, st2 0;char ch[2];for(i 1;i 9; i) {scanf(%s, ch);if(ch[0] W) x 1;else if(ch[0] R) x 2;else if(ch[0] B) x 3;else x 4;go go*10 x;if(i (n-1)*3 m) {st1 st1*104;st2 st2*104;}else {st1 st1*101;st2 st2*102;}}if(st1 go) {puts(0); continue;}printf(%d\n, bfs(st1, st2, go));}return 0;
}转载于:https://www.cnblogs.com/pangblog/p/3239133.html
