poj 3131 Cubic Eight-Puzzle 双向广搜 Hash判重
2024-10-18 19:09:32
挺不错的题目，很锻炼代码能力和调试能力~
题意：初始格子状态固定，给你移动后格子的状态，问最少需要多少步能到达，如果步数大于30，输出-1。
由于单向搜索状态太多，搜到二十几就会爆了，所以应该想到双向广搜。
对于每一个格子，我只需要记录上面和前面的格子颜色，因为格子左右移动前面颜色不变上面颜色变了，前后移动的话只是前面和上面的颜色交换了而已，不过写的太挫了。。。应该直接进制压缩一下。。。我还用了两个数来表示前面和上面的颜色，下次把这些搜索题全A了后再回来重新写一下，重写效果也会不错，并不是题目a了这题就好了。
#include <stdio.h>
#include <string.h> #define LL __int64 const int mod = 100007;
struct HASH{
int head[mod+10], 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)%mod+mod)%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*10+a[i];
for(int i = 1;i <= 9; i++) st2 = st2*10+b[i];
} bool judge(int go) {
int ret = 0;
for(int i = 1;i <= 9; i++) ret = ret*10+a[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 a>b?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/3+1, y = now%3;
if(y == 0) y = 3, x--;
for(i = 0;i < 4; i++) {
int xx = x+dx[i];
int yy = y+dy[i];
if(xx < 1 || xx > 3 || yy < 1 || yy > 3) continue;
int then = (xx-1)*3+yy;
swap(a[now], a[then]);swap(b[now], b[then]);
if(i < 2) {
swap(a[now], b[now]);
if(judge(go)) {
return cur.step+1;
}
get_xy(to.st1, to.st2);
to.step = cur.step+1;
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.step+1;
}
get_xy(to.st1, to.st2);
to.step = cur.step+1;
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 = 1<<8;
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*10+4;
id1++;
continue;
}
if((1<<id2) & i) {
for(k = 3;k >= 1; k--) if(k != a[id1]) break;
sum = sum*10+k;
}
else {
for(k = 1;k <= 3; k++) if(k != a[id1]) break;
sum = sum*10+k;
}
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/3+1, y = now%3;
if(y == 0) y = 3, x--;
for(i = 0;i < 4; i++) {
int xx = x+dx[i];
int yy = y+dy[i];
if(xx < 1 || xx > 3 || yy < 1 || yy > 3) continue;
int then = (xx-1)*3+yy;
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.step+1;
int temp = ha1.isin(to.st1, to.st2);
if(temp >= 0) {
ok = 1;
ans = min(ans, temp+to.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.step+1;
int temp = ha1.isin(to.st1, to.st2);
if(temp >= 0) {
ok = 1;
ans = min(ans, temp+to.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*10+4;
st2 = st2*10+4;
}
else {
st1 = st1*10+1;
st2 = st2*10+2;
}
}
if(st1 == go) {
puts("0"); continue;
}
printf("%d\n", bfs(st1, st2, go));
}
return 0;
}
最新文章
- Ubuntu 16.04 LAMP server 指南 - 配置 Apache2.4,PHP7,和MariaDB（而不是MySQL）
- 删除hao123这个恶心的毒瘤
- .NET: C#: System.Diagnostics
- c 标签
- 【转】解析Java finally
- Delphi程序自删除的几种方法
- shell字符串长度
- Java命令学习系列（7）：Javap（转）
- MyEclipse新建Web Project报错
- Data_Struct(LinkList)
- 007 linux环境下的伪分布式环境搭建
- arcmap发布服务报错：“Faild to publish service”
- 【转载】maven pom详解（2）
- hive查询遇到java.io.EOFException: Unexpected end of input stream错误
- [转]NSIS：判断D盘存在与否确定安装路径
- 由于C++类库版本不同导致的OpenCV编译链接错误
- Opening Default document on IIS （HTML With WebAPI）
- jQuery-处理css样式
- python的变量，对象的内存地址以及参数传递过程
- 在线浏览office 文件