#define DeBUG
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <
string>
#include <
set>
#include <sstream>
#include <map>
#include <bitset>
#include<time.h>
using namespace std ;
#define zero {0}
#define INF 2000000000
#define EPS 1e-6
typedef long long LL;
const double PI = acos(-
1.0);
inline int sgn(
double x)
{
return fabs(x) < EPS ?
0 :(x <
0 ? -
1 :
1);
}
int n;
//n*n
struct MAP
{
int mp[
10][
10];
//状态
int step[
100];
//回溯方向
int stepnum;
//步数
int x,y;
//保存当前0位置
inline
bool operator ==(
const MAP &
a)
{
for(
int i=
1; i<=n; i++
)
for(
int j=
1; j<=n; j++
)
{
if(mp[i][j]!=
a.mp[i][j])
return false;
}
return true;
}
};
MAP origin;//初始态
MAP goal;
int dir[
4][
2]= {
0,
1,
0,-
1,-
1,
0,
1,
0};
void Reset()
{
memset(origin.mp,-
1,
sizeof(origin.mp));
int num=
1;
for(
int i=
1; i<=n; i++
)
{
for(
int j=
1; j<=n; j++
)
{
origin.mp[i][j]=num++
;
}
}
origin.mp[n][n]=
0;
origin.x=
n;
origin.y=
n;
memset(origin.step,-
1,
sizeof(origin.step));
origin.stepnum=
0;
}
int maxx=
1;
MAP bfs()
{
queue<MAP>
Q;
Q.push(origin);
MAP now;
int m,k;
while(!
Q.empty())
{
now=
Q.front();
Q.pop();
int len=
now.stepnum;
// printf("%d %d\n",len+1,maxx++);
m=
now.y;
k=
now.x;
for(
int l=
0; l<
4; l++
)
{
if((l==
0&&now.step[len-
1]==
1)||
(l==
1&&now.step[len-
1]==
0)||
(l==
2&&now.step[len-
1]==
3)||
(l==
3&&now.step[len-
1]==
2))
continue;
int ni=m+dir[l][
0];
int nj=k+dir[l][
1];
if(now.mp[ni][nj]>=
0)
{
swap(now.mp[m][k],now.mp[ni][nj]);
now.step[now.stepnum++]=
l;
now.x=
nj;
now.y=
ni;
if(now==
goal)
{
// printf("%d\n",now.stepnum);
// printf("Time used = %.0lf ms\n",(double)(1000*clock()/CLOCKS_PER_SEC));//**********************
// system("pause");
return now;
}
else
{
Q.push(now);
now.x=
k;
now.y=
m;
now.stepnum--
;
now.step[len]=-
1;
swap(now.mp[m][k],now.mp[ni][nj]);
}
}
}
}
printf("%d\n",now.stepnum);
return now;
}
int main()
{
#ifdef DeBUGs
freopen("C:\\Users\\Sky\\Desktop\\1.in",
"r",stdin);
// freopen("C:\\Users\\Sky\\Desktop\\打表.txt","w",stdout);//PLEASE DELETE IT!!!!!!!!!!!!!!!!!!!!!!!!
#endif
while(scanf(
"%d", &n)+
1)
{
MAP it;
Reset();
for(
int i=
1; i<=n; i++
)
{
for(
int j=
1; j<=n; j++
)
{
scanf("%d", &
goal.mp[i][j]);
}
}
it=
bfs();
printf("%d\n",it.stepnum);
for(
int i=it.stepnum-
1;i>=
0;i--
)
{
switch(it.step[i])
{
case 0:
printf("l");
break;
case 1:
printf("r");
break;
case 2:
printf("d");
break;
case 3:
printf("u");
break;
default:
printf("kao");
}
}
printf("\n");
}
return 0;
}
/*
3
5 1 3
4 2 6
0 7 8
3
6 2 8
1 0 3
4 7 5
3
2 7 3
1 8 4
5 0 6
3
7 5 3
1 0 4
2 8 6
3
3 4 1
0 2 6
7 5 8
3
3 1 5
2 0 8
4 7 6
3
1 5 2
7 4 8
0 6 3
3
4 0 8
5 6 1
7 3 2
3
4 5 0
2 3 1
7 8 6
3
2 6 8
4 5 7
1 3 0
3
1 2 3
4 5 6
7 0 8
8
uurdldrr
16
rullddrrulurdldr
13
uuldrrdllurdr
20
rdlulurdldrulurdldrr
15
urrdllurdrulddr
14
uldrrullddrurd
10
urrdluurdd
17
rddluurddlulurrdd
12
dlurdllurdrd
20
uldruuldldrruulldrdr
1
r
请按任意键继续. . .
*/
View Code
转载于:https://www.cnblogs.com/Skyxj/p/3390002.html
相关资源：数据结构—成绩单生成器
