# UESTC 485 Game（康托，BFS）

Today I want to introduce an interesting game to you. Like eight puzzle, it is a square board with 9 positions, but it filled by 9 numbered tiles. There is only one type of valid move, which is to rotate one row or column. That is, three tiles in a row or column are moved towards the head by one tile and the head tile is moved to the end of the row or column. So it has 12 different moves just as the picture left. The objective in the game is to begin with an arbitrary configuration of tiles, and move them so as to get the numbered tiles arranged as the target configuration.

Now the question is to calculate the minimum steps required from the initial configuration to the final configuration. Note that the initial configuration is filled with a permutation of 1 to 9, but the final configuration is filled with numbers and `*` (which can be any number).

Input

The first line of input contains an integer T (T≤1000), which is the number of data sets that follow.

There are 6 lines in each data set. The first three lines give the initial configuration and the next three lines give the final configuration.

Output

For every test case, you should output `Case #k:` first, where k indicates the case number and starts at 1. Then the fewest steps needed. If he can’t move to the end, just output `No Solution!` (without quotes).

Sample Input

2  1 2 3  4 5 6  7 8 9  1 2 3  4 5 6  7 9 8  1 2 3  4 5 6  7 8 9  8 * 9  5 3 7  2 * *

Sample Output

Case #1: No Solution!

Case #2: 7

http://blog.csdn.net/dacc123/article/details/50952079

```#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <queue>

using namespace std;
struct Node
{
int a[5][5];
int sta;
};
queue<Node> q;
int b[10];
int fac[10];
int vis[400000];
int pre[400000];
int ans;
int f1[10];
int f2[10];
int tran[10];
char ch[10];
bool used[10];
Node cyk;
void facfun()
{
fac[0]=1;
for(int i=1;i<=9;i++)
{
fac[i]=i*fac[i-1];
}
}
int kt(Node q)
{
int cnt=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
b[++cnt]=q.a[i][j];
int sum=0,num=0;
for(int i=1;i<=9;i++)
{
num=0;
for(int j=i+1;j<=9;j++)
{
if(b[i]>b[j])
num++;
}
sum+=num*fac[9-i];
}
return sum;
}
void bfs(Node t)
{
q.push(t);
vis[t.sta]=1;
pre[t.sta]=0;
while(!q.empty())
{
Node term=q.front();
q.pop();
for(int i=1;i<=12;i++)
{

Node temp=term;
if(i<=3)
{
temp.a[i][1]=term.a[i][3];
temp.a[i][2]=term.a[i][1];
temp.a[i][3]=term.a[i][2];
}
else if(i>3&&i<=6)
{
temp.a[i-3][1]=term.a[i-3][2];
temp.a[i-3][2]=term.a[i-3][3];
temp.a[i-3][3]=term.a[i-3][1];
}
else if(i>6&&i<=9)
{
temp.a[1][i-6]=term.a[3][i-6];
temp.a[2][i-6]=term.a[1][i-6];
temp.a[3][i-6]=term.a[2][i-6];
}
else if(i>9&&i<=12)
{
temp.a[1][i-9]=term.a[2][i-9];
temp.a[2][i-9]=term.a[3][i-9];
temp.a[3][i-9]=term.a[1][i-9];
}
int state=kt(temp);
if(vis[state])
continue;

temp.sta=state;
vis[state]=1;
pre[state]=pre[term.sta]+1;

q.push(temp);
}

}
}
void init()
{
memset(vis,0,sizeof(vis));
memset(pre,-1,sizeof(pre));
facfun();
Node st;int cnt=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
st.a[i][j]=++cnt;
st.sta=0;
bfs(st);
}
int anspos;
void dfs(int i)
{
if(i==10)
{
/*for(int p=1;p<=3;p++)
{
for(int k=1;k<=3;k++)
{
cout<<cyk.a[p][k]<<" ";
}
cout<<endl;
}*/
int c=pre[kt(cyk)];
if(c==-1) return;
ans=min(ans,c);return;
}
if(f2[i]==0)
{
for(int j=1;j<=9;j++)
{
if(!used[j])
{
used[j]=true;
int y=i%3,x;
if(y==0){x=i/3;y=3;}
else {x=i/3+1;}
cyk.a[x][y]=j;
dfs(i+1);
used[j]=false;
}
}
}
else
{
int y=i%3,x;
if(y==0){x=i/3;y=3;}
else {x=i/3+1;}
cyk.a[x][y]=f2[i];
dfs(i+1);
}

}

int main()
{
int t;
scanf("%d",&t);
init();
int cas=0;
while(t--)
{
memset(used,0,sizeof(used));
for(int i=1;i<=9;i++)
{
scanf("%d",&f1[i]);
tran[f1[i]]=i;
}
for(int i=1;i<=9;i++)
{
scanf("%s",ch);
f2[i]=ch[0]-'0';
if(f2[i]>=1&&f2[i]<=9)
f2[i]=tran[f2[i]],used[f2[i]]=true;
else
f2[i]=0;
}
ans=1000000;
dfs(1);
if(ans>=1000000)
printf("Case #%d: No Solution!\n",++cas);
else
printf("Case #%d: %d\n",++cas,ans);
}
return 0;
}```

512 篇文章46 人订阅

0 条评论

## 相关文章

29770

### 14、Iterator跟ListIterator的区别

14、Iterator与ListIterator的区别       在使用List,Set的时候，为了实现对其数据的遍历，会经常使用到Iterator(跌代器)...

20200

66460

58240

20760

9420

54070

### C++ 高级语法学习与总结（代码实例）

C++11增加了许多的特性，auto就是一个很明显的例子。  还有就是typedid（）获取数据变量的类型     看下面简短的代码：         ...

35960

17950

### LeetCode84.柱状图中最大的矩形

单调栈板子题，创建一个单调递增栈（栈底到栈顶是递增的），栈内存放的数组下标，遍历数组，将下标存进栈内，以样例来说  首先栈空，0直接进栈；然后因为num...

9620