学步园

简单的BFS，主要是要用hash来判重，其他的不多说，上代码。

AC代码如下：

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

#define MAXN 1000007

typedef struct{
	int x, y;
}Point;

typedef struct{
	int map[4][8];
	int step;
	Point p[4];
}Node;
Node start;
bool flag;
int finals[4][8] = { { 11, 12, 13, 14, 15, 16, 17, 0 }, 
					 { 21, 22, 23, 24, 25, 26, 27, 0 },
					 { 31, 32, 33, 34, 35, 36, 37, 0 },
					 { 41, 42, 43, 44, 45, 46, 47, 0 } };
__int64 endvalue;
__int64 Base[33];
__int64 hashs[MAXN];

//插入hash值
bool HashInsert( __int64 n ){
	int v = n % MAXN;
	while( hashs[v] != -1 && hashs[v] != n ){
		v = ( v + 10 ) % MAXN;
	}
	if( hashs[v] == -1 ){
		hashs[v] = n;
		return true;
	}
	return false;
}

//计算hash值
__int64 calculate( Node &n ){
	__int64 ans = 0;
	for( int i = 0; i < 4; i++ ){
		for( int j = 0; j < 8; j++ ){
			ans += n.map[i][j] * Base[ i * 8 + j ];
		}
	}
	if( ans == endvalue ){
		flag = true;
	}
	return ans;
}

//判断能否插入
bool insert( Node &n ){
	__int64 val = calculate( n );
	return HashInsert( val );
}

int BFS(){
	queue<Node> q;
	start.step = 0;
	q.push( start );
	while( !q.empty() ){
		Node n = q.front();
		q.pop();
		for( int k = 0; k < 4; k++ ){
			for( int i = 0; i < 4; i++ ){
				for( int j = 0; j < 8; j++ ){
					if( n.map[i][j] == 0 ){
						continue;
					}
					if( n.map[i][j] != n.map[n.p[k].x][n.p[k].y-1] + 1 ){
						continue;
					}
					Node temp = n;
					swap( temp.map[i][j], temp.map[n.p[k].x][n.p[k].y] );
					if( insert( temp ) ){
						temp.step += 1;
						temp.p[k].x = i;
						temp.p[k].y = j;
						q.push( temp );
						if( flag ){
							return temp.step;
						}
					}
				}
			}
		}
	}
	return -1;
}

int main(){
	int T;
	cin >> T;

	Base[0] = 1;
	for( int i = 1; i < 33; i++ ){
		Base[i] = Base[i-1] * 2;
	}
	endvalue = 0;
	for( int i = 0; i < 4; i++ ){
		for( int j = 0; j < 8; j++ ){
			endvalue += finals[i][j] * Base[ i * 8 + j ];
		}
	}

	while( T-- ){
		memset( start.map, 0, sizeof( start.map ) );
		int k = 0;
		for( int i = 0; i < 4; i++ ){
			for( int j = 1; j < 8; j++ ){
				cin >> start.map[i][j];
				if( start.map[i][j] % 10 == 1 ){
					start.map[i][j] = 0;
					start.p[k].x = i;
					start.p[k++].y = j;
				}	
			}
		}
		start.map[0][0] = 11;
		start.map[1][0] = 21;
		start.map[2][0] = 31;
		start.map[3][0] = 41;
		flag = false;
		memset( hashs, -1, sizeof( hashs ) );
		if( calculate( start ) == endvalue ){
			cout << 0 << endl;
		}else{
			cout << BFS() << endl;
		}
	}
	return 0;
}