[Vijos1898]学姐吃生鱼片 解题报告

这道题思路挺简洁的，但却绝对足够让我耳目一新了。

一、题意

描述

学姐今晚想吃生鱼片, doc便领着她去吃啦. 但是怎么能这样轻易就让馋嘴的学姐吃到生鱼片呢!

于是doc准备了一个"二维魔方".
所谓 二维魔方, 可以被考虑为平面上 3X3 的方格, 里面不重复得填有 1~9 共9个数字.
每一次可以对某一行或某一列向某一方向做轮换操作, 比如说, 如果第三列原来的数字依次为 3 6 9, 那么针对第三列向上轮换一次后 就变成了: 6 9 3; 再向上轮换一次后 就变成了9 3 6.
现在doc给出了 二维魔方的初始状态, 再给出目标状态. 初始状态是由1~9组成的 3X3 的数字方格, 而目标状态中某个位置被标记为星号, 表示可以是任意数字.
如果学姐能用最少的操作次数得到目标状态, doc就会喂她吃一小块生鱼片呢!

格式

输入格式

第一行一个整数T, 表示总的询问次数.
之后有T次询问, 对于每一次询问, 有6行, 每行3组字符(包括数字1~9和星号)以空格隔开.

输出格式

对于每一次询问, 输出一行.
首先输出询问的标号(参见样例输出), 之后输出最少的操作次数. 如果不可能做到, 输出"No Solution!"(不输出引号).

样例1

样例输入1[复制]

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

样例输出1[复制]

Case #1: 7
Case #2: No Solution!

限制

对于30%的数据, T <= 3
对于60%的数据, T <= 100
对于100%的数据, T <= 1000

二、题解

看到它我起初完全没有思路，只能暴搜，然后看了看题解，题解就一句话：一遍预处理BFS。

什么玩意儿！完全看不懂，啥叫一遍预处理？咋预处理啊？它初始状态和目标状态全不一样啊！

然后我问了ljs学长，终于搞明白了。。

学长说：虽然这么多初始状态，但是它们本质上都是一样的！

原来虽然这么多初始状态是不一样的，但是我们可以都将其映射到某一特定排列，例如123456789,然后令目标状态以同样的方式映射即可。这样的话，就把多源最短路优化成了单源最短路 ！

做到这里，不仅想到约瑟夫问题和地精部落，同样是1~N的排列，同样的思想，同样的神奇！

①排列是可以离散的！在以后的学习中，处理排列问题时我想我必须牢牢记住这一点；在排列问题中，离散排列总是具有化腐朽为神奇的力量。

三、BFS中的代码技巧

1、用循环和函数来代替繁杂的拓展过程；

2、用交换来代替题意中蛋疼的旋转魔方。

3、②千万不要忘记回溯！随时思考变量的意义！

4、③如果写代码过程中突然想到了某些优化或更改，最好把它写下来；否则很可能改了这边忘了那边，导致程序出现差错。

5、④不要忘了编制数据和对拍。数据和代码一样重要！

#include
using namespace std;
#include
#include
#include
#include
char * ptr=(char *)malloc(100000);
inline void in(int &x){
	while(*ptr<'0'||*ptr>'9')++ptr;
	x=0;
	while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
#define J9 362880
int q[J9][9]={1,2,3,4,5,6,7,8,9},ni[]={1,1,2,6,24,120,720,5040,40320},dis[J9],ans[J9],h,t,Ans;
bool p[J9],tmp[10];
int kangtuo(int a[]){
	bool p[10];
	int sum,ans=0,i,j;
	memset(p,1,sizeof(p));
	for(i=0;i<9;++i){
		sum=0;
		for(j=1;j			sum+=p[j];
		ans+=sum*ni[8-i];
		p[a[i]]=0;
	}
	return ans;
}
inline void add(int a[]){
	int kt=kangtuo(a);
	if(p[kt])return;
	p[kt]=1;
	memcpy(q[t],a,9*sizeof(int));
	dis[t]=dis[h]+1;
	ans[kt]=dis[t++];
}
inline void build(int x){
	if(x==9){
		Ans=min(Ans,ans[kangtuo(q[0])]);
		return;
	}
	if(q[0][x]+1)build(x+1);
	else{
		for(int i=1;i<10;++i)
			if(!tmp[i]){
				q[0][x]=i;
				tmp[i]=1;
				build(x+1);
				tmp[i]=0;
			}
		q[0][x]=-1;
	}
}
inline void inchr(int &x){
	while((*ptr<'0'||*ptr>'9')&&*ptr!='*')++ptr;
	x=*ptr=='*'?-1:*ptr-'0';
	++ptr;
}
int main(){
	int i,kt,X,T;
	/*------Prework-----*/
	memset(ans,127,sizeof(ans));
	t=1;
	kt=kangtuo(q[0]);
	p[kt]=1;
	ans[kt]=0;
	for(h=0;h!=t;++h){
		/*--Change in row---*/
		for(i=3,X=1;i--;X+=3){
			swap(q[h][X-1],q[h][X+1]);
			/*---Direction I--*/
			swap(q[h][X-1],q[h][X]);
			add(q[h]);
			swap(q[h][X-1],q[h][X]);
			/*---Direction II--*/
			swap(q[h][X],q[h][X+1]);
			add(q[h]);
			swap(q[h][X],q[h][X+1]);
			
			swap(q[h][X-1],q[h][X+1]);
		}
		/*--Change in line---*/
		for(i=3,X=3;i--;++X){
			swap(q[h][X-3],q[h][X+3]);
			/*---Direction I--*/
			swap(q[h][X-3],q[h][X]);
			add(q[h]);
			swap(q[h][X-3],q[h][X]);
			/*---Direction II--*/
			swap(q[h][X],q[h][X+3]);
			add(q[h]);
			swap(q[h][X],q[h][X+3]);
			
			swap(q[h][X-3],q[h][X+3]);
		}
	}
	/*--Read and Work Out--*/
	fread(ptr,1,100000,stdin);
	in(T);
	int point[10];
	bool flag;
	for(int k=1;k<=T;++k){
		memset(tmp,0,sizeof(tmp));
		for(i=1;i<10;++i){
			inchr(X);
			point[X]=i;
		}
		flag=1;
		for(i=0;i<9;++i,++ptr){
			inchr(q[0][i]);
			if(q[0][i]+1){
				flag=0;
				q[0][i]=point[q[0][i]];
				tmp[q[0][i]]=1;
			}
		}
		if(flag){
			printf("Case #%d: 0\n",k);
			continue;
		}
		Ans=0x7fffffff;
		build(0);
		printf("Case #%d: ",k);
		if(Ans<100000000)printf("%d",Ans);
		else printf("No Solution!");
		printf("\n");
	}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！