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

利用康托展开

把所有状态bfs一次,

然后再去做

利用康托展开进行bfs预处理。题目给的一个起始的九宫格,和一个目标的九宫格。 不能直接用目标的九宫格去找起始的九宫格,会超时,应该根据把起始九宫格当作  1 2 3  4 5 6  7 8 9  然后确定目标九宫格是怎么样的,这样就可以直接用之前打的表了。预处理就是处理1 2 3 4 5 6 7 8 9到每种九宫格的步数

#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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏拭心的安卓进阶之路

Java 集合深入理解(11):LinkedList

今天心情鱼肚白,来学学 LinkedList 吧! 日常开发中,保存一组数据使用的最多的就是 ArrayList, 其次就是 LinkedList 了。 我们...

29770
来自专栏海说

14、Iterator跟ListIterator的区别

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

20200
来自专栏非著名程序员

解决TextView排版混乱或者自动换行的问题

其实在TextView中遇到排版自动换行而导致混乱不堪的情况是非常常见的,而且导致这种问题产生的原因就是英文和中文混合输入,半角字符和全角字符混合在一起了。一般...

66460
来自专栏cmazxiaoma的架构师之路

浅谈CGLIB动态代理和JDK动态代理 学习笔记

58240
来自专栏葡萄城控件技术团队

深入浅出OOP(四): 多态和继承(抽象类)

在本文中,我们讨论OOP中的热点之一:抽象类。抽象类在各个编程语言中概念是一致的,但是C#稍微有些不一样。本文中我们会通过代码来实现抽象类,并一一进行解析。 A...

20760
来自专栏行者常至

009.多线程-AtomicInteger

版权声明:本文为博主原创文章,允许转载,请标明出处。

9420
来自专栏电光石火

3X3 九宫格

题目:3X3 的九宫格,每个横竖斜相加都等于15,使用1-9数字。 要求:PHP语言,1-9数字不重复。 解题思路分析: 1:可以知道和为15,所以获...

54070
来自专栏ml

C++ 高级语法学习与总结(代码实例)

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

35960
来自专栏我的技术专栏

数据结构图文解析之:栈的简介及C++模板实现

17950
来自专栏mathor

LeetCode84.柱状图中最大的矩形

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

9620

扫码关注云+社区

领取腾讯云代金券