蓝桥杯历届试题-九宫重排(C++)

解题思路:
暴力搜索,然后去掉重复的图,九宫格最多的排列组合也就是9!,也就是说最多一共362880种,本题使用使用100000的数组可以拿到50%的分,150000的数组可以拿到67%的分,200000的数组可以拿到100%的分,也没到达362880,也就是说以最大种类为上界是完全可以拿到全部分的,

注意事项:
这里要注意定义大数组要在全局变量里定义,我用的DEV局部变量string类型定义200000个是会崩溃的,以下是详细代码.

参考代码:

#include<bits/stdc++.h>
using namespace std;

string arr[200000],beg,des;
int dis[200000],front,rear,pos;
int main() {
	set<string>s;
	cin>>beg>>des;
	if(beg==des) {
		cout<<0<<endl;
		return 0;
	}
	s.insert(beg);
	int dalta[4]= {-1,1,-3,3};
	arr[front]=beg;
	while(front<=rear) {
		beg=arr[front];
		for(pos=0; pos<9; pos++)if(beg[pos]=='.')break;
		for(int i=0; i<4; i++) {
			if(pos==0||pos==1||pos==2)if(i==2)continue;
			if(pos==6||pos==7||pos==8)if(i==3)continue;
			if(pos==0||pos==3||pos==6)if(i==0)continue;
			if(pos==2||pos==5||pos==8)if(i==1)continue;
			int p=pos+dalta[i];
			char c=beg[pos];
			beg[pos]=beg[p];
			beg[p]=c;
			if(s.count(beg)==0) {
				s.insert(beg);
				arr[++rear]=beg;
				dis[rear]=dis[front]+1;
				if(beg==des) {
					cout<<dis[rear]<<endl;
					return 0;
				}
			}
			c=beg[pos];
			beg[pos]=beg[p];
			beg[p]=c;
		}
		front++;
	}
	cout<<-1<<endl;
	return 0;
}