WOJ132Squares（BFS+打表）

上来拿个1<<10勋章…

题目链接：woj132

Description

Consider a 3 by 3 arrangement of the digits 1 to 9, as illustrated in the following diagram:
1 3 5
8 7 6
4 9 2
Figure 1
The arrangement can by modified by rotating any of the 2-by-2 groups in the corners, either clockwise or anticlockwise. Thus if the top-right
corner of the above arrangement is rotated anticlockwise, the result is the following arrangement:
1 5 6
8 3 7
4 9 2
Figure 2
A magic square is an n-by-n arrangement of numbers, such that the sum of the numbers in each row, column, and diagonal is the same. For
example, the following diagram illustrates one possible 3-by-3 magic square for the numbers 1 to 9:
8 1 6
3 5 7
4 9 2
Figure 3
Your task is to determine the minimum number of moves to trans-form a given digit arrangement into a magic square.
For example, the magic square in Figure 3 can be obtained from the arrangement illustrated in Figure 2 by one clockwise rotation of the top-
left corner. Thus the arrangement given in Figure 1 can be transformed into a magic square in 2 moves (and, as you can verify, no shorter
sequences of moves would suffice).

Input

Input will consist of a series of lines, each specifying an initial arrangement of the digits 1 to 9, listed in row-by-row order. The end of
the input is indicated by a line that consists of the word END.

Output

Output for each arrangement should consist of either:

1. The minimum number of moves followed by a single space and then the word “moves”, or
2. The word “IMPOSSIBLE”, if it is not possible to achieve a magic square arrangement.

Sample Input

135876492
438975261
672159834
129764583
END

Sample Output

2 moves
1 moves
0 moves
4 moves

题目大意：给一个三阶矩阵，问能不能通过旋转任意一个二阶子阵（注意是相邻），经过若干次旋转得到一个三阶幻方。

题目思路：三阶幻方有8种，由于9个数字的全排列规模在3e5左右，显然合法的能到达幻方状态的个数必然小于这个规模，于是可以bfs处理一张表处理，然后通过查表解答。由于bfs的性质，最早生成的状态一定是最优解，比如某个状态可以由两种幻方转出来，但他存的步数一定是最先生成他的那个步数，后面形成的一定没前面的优秀。

Code：

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

int Max;
long long res;
unordered_map<long long, long long> vis;
queue<pair<long long, int> > q;
long long st[8] = {492357816,294753618,834159672,438951276,618753294,816357492,276951438,672159834};
int op[4][4] = {
	0,3,4,1,
	1,4,5,2,
	3,6,7,4,
	4,7,8,5
};

void add(long long now, int op[4], int step) {
	long long arr1[9], arr2[9];
	for(int i=0; now!=0; i++) {
		arr2[8-i]=arr1[8-i]= now % 10;
		now /= 10;
	}
	
	long long tmp = arr1[op[3]];
	for(int i=3; i>=1; i--) arr1[op[i]] = arr1[op[i-1]];
	arr1[op[0]] = tmp;
	
	tmp = arr2[op[0]];
	for(int i=0; i<=2; i++) arr2[op[i]] = arr2[op[i+1]];
	arr2[op[3]] = tmp;
	
	long long cur1=0, cur2=0;
	for(int i=8; i>=0; i--) {
		cur1 = cur1*10 + arr1[i];
		cur2 = cur2*10 + arr2[i];
	}
	if(!vis.count(cur1)) {
		q.push(make_pair(cur1, step));
		vis.insert(make_pair(cur1, step));
	}
	if(!vis.count(cur2)) {
		q.push(make_pair(cur2, step));
		vis.insert(make_pair(cur2, step));
	}
}

void bfs() {
	vis.clear();
	while(!q.empty()) q.pop();
	for(int i=0; i<8; i++) q.push(make_pair(st[i], 0)), vis.insert(make_pair(st[i], 0));
	while(!q.empty()) {
		pair<long long, int> cur = q.front(); q.pop();
		for(int i=0; i<4; i++) add(cur.first, op[i], cur.second+1);
	}
}

int main() {
	string cmd;
	bfs();
	while(cin >> cmd && cmd[0]!='E') {
		res = 0;
		for(int i=0; i<9; i++) res = res*10 + (cmd[i]-'0');
		if(!vis.count(res))
			cout << "IMPOSSIBLE" << endl;
		else
			cout << vis[res] << " moves" << endl;
	}
	return 0;
}