HDU 1403 Eight&POJ 1077(康拖，A* ,BFS,双广)
HDU 1403 Eight&POJ 1077(康拖，A* ,BFS,双广)
Eight
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 18153 Accepted Submission(s): 4908 Special Judge
Problem Description The 15-puzzle has been around for over 100 years; even if you don’t know it by that name, you’ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let’s call the missing tile ‘x’; the object of the puzzle is to arrange the tiles so that they are ordered as:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x
where the only legal operation is to exchange ‘x’ with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8 9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12 13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x r-> d-> r->
The letters in the previous row indicate which neighbor of the ‘x’ tile is swapped with the ‘x’ tile at each step; legal values are ‘r’,’l’,’u’ and ‘d’, for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing ‘x’ tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three arrangement.
Input You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus ‘x’. For example, this puzzle
1 2 3 x 4 6 7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output You will print to standard output either the word “unsolvable”, if the puzzle has no solution, or a string consisting entirely of the letters ‘r’, ‘l’, ‘u’ and ‘d’ that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.
Sample Input 2 3 4 1 5 x 7 6 8
Sample Output ullddrurdllurdruldr
解决这道题目，有很多方法，比如双广，BFS打表，A*+简单估价函数，A*+曼哈顿距离，IDA*+曼哈顿距离。但是这些方法都是基于在康托展开的基础上，别的状态表示都会超时。关于康托展开给出一篇博客把 http://blog.csdn.net/Dacc123/article/details/50952079
还有这道题目在poj和hdu上的测试数据是不同的，hdu上的数据比较多吧，poj水一点。
双广，从起始和结尾同时bfs，用康托展开表示状态 hdu看数据的，有的时候是可以过的4960ms。双广还是效率比较低的，poj 188ms
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <queue>
#include <map>
#include <string>
using namespace std;
struct Node
{
int a[3][3];
int x,y;
int state,id;
Node(){};
Node(int a[3][3],int x,int y,int state,int id)
{
this->id=id;
this->x=x;
this->y=y;
this->state=state;
memcpy(this->a,a,sizeof(this->a));
}
};
queue<Node>q;
string f[2][500000];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int fac[10];
int s[2];
char m[2][5]={"udlr","durl"};
char str[105];
void facfun()
{
fac[0]=1;
for(int i=1;i<=9;i++)
fac[i]=fac[i-1]*i;
}
int kangtuo(int a[3][3])
{
int sum=0,num;
for(int i=0;i<9;i++)
{
num=0;
for(int j=i+1;j<9;j++)
{
if(a[i/3][i%3]>a[j/3][j%3])
num++;
}
sum+=num*fac[8-i];
}
return sum;
}
bool isok(int a[3][3])
{
int num=0;
for(int i=0;i<9;i++)
{
for(int j=i+1;j<9;j++)
{
if(a[i/3][i%3]!=9&&a[j/3][j%3]!=9&&a[i/3][i%3]>a[j/3][j%3])
num++;
}
}
return !(num&1);
}
void bfs(Node st,Node ed)
{
memset(f,0,sizeof(f));
q.push(st);q.push(ed);
s[1]=st.state;s[0]=ed.state;
f[1][s[1]]=""; f[0][s[0]] = "";
while(!q.empty())
{
Node term=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=term.x+dir[i][0];
int yy=term.y+dir[i][1];
if(xx<0||xx>=3||yy<0||yy>=3)
continue;
swap(term.a[xx][yy],term.a[term.x][term.y]);
int state=kangtuo(term.a);
if(!f[term.id][state][0])
{
if(term.id)
f[term.id][state]=f[term.id][term.state]+m[term.id][i];
else
f[term.id][state]=m[term.id][i]+f[term.id][term.state];
if(f[1-term.id][state][0])
{
cout<<f[1][state]<<f[0][state]<<endl;
return;
}
else
q.push(Node(term.a,xx,yy,state,term.id));
}
swap(term.a[xx][yy],term.a[term.x][term.y]);
}
}
//printf("unsolvable\n");
}
int main()
{
while(gets(str))
{
while(!q.empty())
q.pop();
facfun();
Node st;
int len=strlen(str);
int cot=0;
for(int i=0;i<len;i++)
{
if(str[i]!=' ')
{
if(str[i]=='x')
{
st.a[cot/3][cot%3]=9;
st.x=cot/3;st.y=cot%3;
}
else
st.a[cot/3][cot%3]=str[i]-'0';
cot++;
}
}
st.id=1;st.state=kangtuo(st.a);
Node ed;
cot=1;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
ed.a[i][j]=cot++;
ed.x=2;ed.y=2;ed.id=0;ed.state=kangtuo(ed.a);
if(!isok(st.a))
{
printf("unsolvable\n");
continue;
}
bfs(st,ed);
}
return 0;
}BFS打表:从结果往前面扫，把每一种状态到结果的步数记录下来。 hdu 109ms poj 989ms
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <map>
#include <queue>
using namespace std;
int fac[]={1,1,2,6,24,120,720,5040,40320};
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Node
{
int a[5][5];
int posx;
int posy;
int sta;
};
queue<Node> q;
bool vis[400000];
int res[400000];
int pre[400000];
char s[100];
int a1[100];
int a2[10];
map<int,char>m;
int kt(Node s)
{
int cot=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
a2[++cot]=s.a[i][j];
int sum=0,num;
for(int i=1;i<=9;i++)
{
num=0;
for(int j=i+1;j<=9;j++)
{
if(a2[i]>a2[j])
num++;
}
sum+=num*fac[9-i];
}
return sum;
}
void bfs(Node a)
{
q.push(a);
vis[0]=1;
while(!q.empty())
{
Node term=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=term.posx+dir[i][0];
int yy=term.posy+dir[i][1];
if(xx<1||xx>3||yy<1||yy>3)
continue;
Node temp=term;
swap(temp.a[temp.posx][temp.posy],temp.a[xx][yy]);
temp.posx=xx;temp.posy=yy;
int state=kt(temp);temp.sta=state;
if(vis[state])
continue;
pre[state]=term.sta;
res[state]=i;
vis[state]=1;
q.push(temp);
}
}
}
void fun(int term)
{
if(term==0)
return;
cout<<m[res[term]];
fun(pre[term]);
}
int main()
{
m[0]='u';m[1]='d';m[2]='l';m[3]='r';
int cnt=1;
Node t;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
t.a[i][j]=cnt++;
t.posx=3;t.posy=3;t.sta=0;
memset(vis,0,sizeof(vis));
vis[0]=1;
bfs(t);
while(gets(s))
{
int x,y;
int len=strlen(s);
int cot=0;
Node t3;
for(int i=0;i<len;i++)
{
if(s[i]!=' ')
{
cot++;
if(cot%3==0) { x=cot/3; y=3;}
else { x=cot/3+1; y=cot%3;}
if(s[i]=='x')
t3.a[x][y]=9;
else
t3.a[x][y]=s[i]-'0';
}
}
int target=kt(t3);
if(!vis[target])
printf("unsolvable\n");
else
{
fun(target);
cout<<endl;
}
}
return 0;
}A*+简单估价函数+优先队列 ，这里要加一个判断来对应unsolved，当初始状态的逆序数（除去要移动的版块）和目标状态的同偶或同奇，就一定可以到达，否则一定不能。 简单估价函数：可以以当前状态下，多少个数字的位置是不正确的，表示价值。
hdu 2964ms poj 0ms
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <string>
#include <map>
using namespace std;
#define MAX 400000
struct Node
{
int a[3][3];//图的状态
int x,y;//空格的位置
int state;//康托展开
int g,h;//估价函数g,h
string s;//记录路径
bool operator<(const Node a)const
{
return h==a.h?g>a.g:h>a.h;
}
};
priority_queue<Node> q;
int fac[10];
int vis[MAX+5];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
map<int,char> m;
char c[100];
void facfun()
{
m[0]='d';m[1]='u';m[2]='r';m[3]='l';
fac[0]=1;
for(int i=1;i<=9;i++)
fac[i]=fac[i-1]*i;
}
//康托展开
int kangtuo(int a[3][3])
{
int sum=0,num;
for(int i=0;i<9;i++)
{
num=0;
for(int j=i+1;j<9;j++)
{
if(a[i/3][i%3]>a[j/3][j%3])
num++;
}
sum+=num*fac[8-i];
}
return sum;
}
//简单估价函数
int get(int a[3][3])
{
int num=0;
for(int i=0;i<8;i++)
{
if(a[i/3][i%3]!=i+1)
num++;
}
return num;
}
void bfs(Node st)
{
q.push(st);
vis[st.state]=1;
int sh=st.h;int sg=st.g;
while(!q.empty())
{
Node temp;
Node term=q.top();
q.pop();
if(term.state==0)
{
cout<<term.s<<endl;
return;
}
for(int i=0;i<4;i++)
{
temp=term;
int xx=temp.x+dir[i][0];
int yy=temp.y+dir[i][1];
if(xx<0||xx>2||yy<0||yy>2)
continue;
swap(temp.a[temp.x][temp.y],temp.a[xx][yy]);
temp.x=xx;temp.y=yy;temp.s=term.s+m[i];
temp.g=term.g+1;temp.h=get(temp.a);
temp.state=kangtuo(temp.a);
if(vis[temp.state])
continue;
vis[temp.state]=1;
q.push(temp);
}
}
printf("unsolvable\n");
}
bool isok(int a[3][3])
{
int num=0;
for(int i=0;i<9;i++)
{
for(int j=i+1;j<9;j++)
{
if(a[i/3][i%3]!=9&&a[j/3][j%3]!=9&&a[i/3][i%3]>a[j/3][j%3])
num++;
}
}
if(!(num&1))
return true;
else
return false;
}
int main()
{
while(gets(c))
{
facfun();
while(!q.empty())
{
q.pop();
}
memset(vis,0,sizeof(vis));
int len=strlen(c);
Node start;
int cot=0;
for(int i=0;i<len;i++)
{
if(c[i]!=' ')
{
if(c[i]=='x')
{
start.a[cot/3][cot%3]=9;
start.x=cot/3;start.y=cot%3;
}
else
start.a[cot/3][cot%3]=c[i]-'0';
cot++;
}
}
start.g=0;start.h=get(start.a);start.state=kangtuo(start.a);
start.s="";
if(!isok(start.a))
{
printf("unsolvable\n");
continue;
}
bfs(start);
}
return 0;
}A*+曼哈顿距离+优先队列 股价函数变成了曼哈顿距离 hdu 1450ms poj 0ms
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <string>
#include <map>
using namespace std;
#define MAX 400000
struct Node
{
int a[3][3];//图的状态
int x,y;//空格的位置
int state;//康托展开
int g,h;//估价函数g,h
string s;//记录路径
bool operator<(const Node a)const
{
return h==a.h?g>a.g:h>a.h;
}
};
priority_queue<Node> q;
int fac[10];
int vis[MAX+5];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
map<int,char> m;
char c[100];
void facfun()
{
m[0]='d';m[1]='u';m[2]='r';m[3]='l';
fac[0]=1;
for(int i=1;i<=9;i++)
fac[i]=fac[i-1]*i;
}
//康托展开
int kangtuo(int a[3][3])
{
int sum=0,num;
for(int i=0;i<9;i++)
{
num=0;
for(int j=i+1;j<9;j++)
{
if(a[i/3][i%3]>a[j/3][j%3])
num++;
}
sum+=num*fac[8-i];
}
return sum;
}
//简单估价函数
int get(int a[3][3])
{
int num=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
int x=(a[i][j]-1)/3;
int y=(a[i][j]-1)%3;
num+=abs(x-i)+abs(y-j);
}
}
return num;
}
void bfs(Node st)
{
q.push(st);
vis[st.state]=1;
int sh=st.h;int sg=st.g;
while(!q.empty())
{
Node temp;
Node term=q.top();
q.pop();
if(term.state==0)
{
cout<<term.s<<endl;
return;
}
for(int i=0;i<4;i++)
{
temp=term;
int xx=temp.x+dir[i][0];
int yy=temp.y+dir[i][1];
if(xx<0||xx>2||yy<0||yy>2)
continue;
swap(temp.a[temp.x][temp.y],temp.a[xx][yy]);
temp.x=xx;temp.y=yy;temp.s=term.s+m[i];
temp.g=term.g+1;temp.h=get(temp.a);
temp.state=kangtuo(temp.a);
if(vis[temp.state])
continue;
vis[temp.state]=1;
q.push(temp);
}
}
printf("unsolvable\n");
}
bool isok(int a[3][3])
{
int num=0;
for(int i=0;i<9;i++)
{
for(int j=i+1;j<9;j++)
{
if(a[i/3][i%3]!=9&&a[j/3][j%3]!=9&&a[i/3][i%3]>a[j/3][j%3])
num++;
}
}
if(!(num&1))
return true;
else
return false;
}
int main()
{
while(gets(c))
{
facfun();
while(!q.empty())
{
q.pop();
}
memset(vis,0,sizeof(vis));
int len=strlen(c);
Node start;
int cot=0;
for(int i=0;i<len;i++)
{
if(c[i]!=' ')
{
if(c[i]=='x')
{
start.a[cot/3][cot%3]=9;
start.x=cot/3;start.y=cot%3;
}
else
start.a[cot/3][cot%3]=c[i]-'0';
cot++;
}
}
start.g=0;start.h=get(start.a);start.state=kangtuo(start.a);
start.s="";
if(!isok(start.a))
{
printf("unsolvable\n");
continue;
}
bfs(start);
}
return 0;
}