codevs 1225 八数码难题
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 Description
Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入描述 Input Description
输入初试状态，一行九个数字，空格用0表示
输出描述 Output Description
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)
样例输入 Sample Input
283104765
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
详见试题
分类标签 Tags 点此展开
启发式搜索 广度优先搜索 深度优先搜索 迭代搜索 搜索
/*复杂题目模板加注解*/
# include <stdio.h>
# include <mem.h> # define MAXN ( + ) typedef struct
{
char a[];
}state; const int dir[][] = {{-,}, {,}, {,}, {,-}};
int fact[]; int front, rear;
state cur, nst; /* new state */
char vis[MAXN];
char dist[MAXN]; /* 求的是最短距离( < 100)，可以用 char 类型 */
state Q[MAXN/]; void read(state *s);
int inversions(state s);
int cantor(state s);
void init_fact(void);
int bfs_d(state start, state goal); int main()
{
state start, goal; freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout); init_fact(); read(&start);/*指针引用*/
read(&goal); if (inversions(start)% == inversions(goal)%)/
{/*判断能不能到达最终状态，如果能达到最终状态的话，那么格子中的个数在后面有几个比他小的数的和的奇偶是不变的，无论怎么变换，可以用归纳推理证明*/
printf("%d\n", bfs_d(start, goal));
}
else puts("-1");/*找不到最终的状态*/ return ;
} int bfs_d(state start, state goal)
{
int i, x, y, nx, ny, ct, nt; memset(vis, , sizeof(vis));
memset(dist, , sizeof(dist)); front = ;
Q[front] = start;
rear = ;
Q[rear++] = goal;
vis[cantor(start)] = ; /* 1 表示从起始节点扩展得到 */
vis[cantor(goal)] = ; /* 2 表示从目标节点扩展得到 */ while (front < rear)
{
cur = Q[front++];
ct = cantor(cur);
for (i = ; cur.a[i] && i < ; ++i);/*找出0的位置*/
x = i / ;/*求出0所在的行数列数*/
y = i % ;
for (i = ; i < ; ++i)
{
nx = x + dir[i][];/*把0向四周扩展*/
ny = y + dir[i][];
if (nx>= && nx< && ny>= && ny<)
{
nst = cur;
nst.a[x*+y] = cur.a[nx*+ny];/*互换0的位置与对应元素的位置*/
nst.a[nx*+ny] = ;
if (!vis[nt = cantor(nst)])/*判断当前这个状态是否已经到过*/
{
Q[rear++] = nst;
/* foot[nt] = ct; */
dist[nt] = dist[ct] + ;
vis[nt] = vis[ct];/*转移扩展的方向*/
}
else if (vis[ct] != vis[nt])/*如果已经到过，就是两者变换的次数和加上最后一次变化*/
{/*这是双向广搜的精髓，判断两个点是从不同的方向转移来的*/
return + dist[nt] + dist[ct];
}
}
}
} return -;
} void read(state *s)
{
int i;
char c[]; for (i = ; i < ; ++i)
{
scanf("%s", c);
if (c[] == 'x') (*s).a[i] = ;
else (*s).a[i] = c[] - '';
}
} int inversions(state s)
{
char ch;
int i, j, ret; ret = ;
for (i = ; i < ; ++i)
{
if (s.a[i] == ) continue;
ch = s.a[i];
for (j = i+; j < ; ++j)
{
if (s.a[j] < ch && s.a[j] != )
++ret;
}
} return ret;
} int cantor(state s)/*康托展开应用于哈希表，处理排列问题是不会有冲突的，网上有证明，可以自己看*/
{
char ch;
int i, j, ret, cnt; ret = ;
for (i = ; i < ; ++i)
{
cnt = ;
ch = s.a[i];
for (j = i+; j < ; ++j)
{
if (s.a[j] < ch)
++cnt;
}
ret += cnt*fact[-i];
} return ret;
} void init_fact(void)
{
int i; fact[] = ;
for (i = ; i < ; ++i)
{
fact[i] = i * fact[i-];/*处理阶乘，整张图一共有9!种状态*/
}
}
本题题解：
#define N 3628800
#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
struct state{
char a[];
};
queue<state>que;
int xx[]={,,,-};
int yy[]={,-,,};
int visit[N]={};
int fact[]={};
int dis[N]={};
void init_goal(state& goal)
{
goal.a[]='';goal.a[]='';goal.a[]='';
goal.a[]='';goal.a[]='';goal.a[]='';
goal.a[]='';goal.a[]='';goal.a[]='';
//goal.a="123804765";
//strcpy(goal.a,"123804765");
}
void in_fact()
{
fact[]=;
for(int i=;i<;++i)
fact[i]=i*fact[i-];
}
int cantor(state k)
{
int ret=;
for(int i=;i<;++i)
{
int cnt=;
char ch=k.a[i];
for(int j=i+;j<;++j)
if(ch>k.a[j]) cnt++;
ret+=cnt*fact[-i];
}
return ret;
}
int bfs(state begin,state goal)
{
que.push(begin);que.push(goal);
int k1=cantor(begin);
int k2=cantor(goal);
visit[k1]=;
visit[k2]=;
dis[k1]=;dis[k2]=;
while(!que.empty())
{
state fro=que.front();
int can_fro=cantor(fro);
que.pop();
int i;
for(i=;fro.a[i]!=''&&i<;++i);
int x=i/;
int y=i%;
for(int j=;j<;++j)
{
int nx=x+xx[j],ny=y+yy[j];
if(nx>=&&nx<&&ny>=&&ny<)
{
state now=fro;
now.a[*x+y]=fro.a[*nx+ny];
now.a[*nx+ny]='';
int kj=cantor(now);
if(!visit[kj])
{
que.push(now);
visit[kj]=visit[can_fro];/*转移是正向扩展还是逆向扩展*/
dis[kj]=dis[can_fro]+;
}
else if(visit[kj]!=visit[can_fro])
{/*这是双向广搜的精髓，必须用visit表示当前这个是同时由正反广搜扩展来的*/
return +dis[kj]+dis[can_fro];
}
}
}
}
}
int main()
{
state goal,begin;
init_goal(goal);
in_fact();
// scanf("%s",goal.a+1);
scanf("%s",begin.a);
printf("%d\n",bfs(begin,goal));
return ;
}