Push Box HDU - 1732

Push Box

 HDU - 1732 

Push Box is a classic puzzle game. This game play in a grid, there are five types of block in it, the player, the box, the hole, empty place, and the wall. In every step, player can move up, down, left, or right, if the target place is empty. Moreover, if a box in the target place, and the next place in that direction is empty, player can move to the target place, and then push the box to the next place. Remember, both of the player and boxes can't move out of the grid, or you may assume that there is a wall suround the whole grid. The objective of this game is to push every box to a hole. Now, your problem is to find the strategy to achieve the goal with shortest steps, supposed there are exactly three boxes.

Input

The input consists of several test cases. Each test case start with a line containing two number, n, m(1 < n, m ≤ 8), the rows and the columns of grid. Then n lines follow, each contain exact m characters, representing the type of block in it. (for empty place, X for player, * for box, # for wall, @ for hole). Each case contain exactly one X, three *, and three @. The input end with EOF.

Output

You have to print the length of shortest strategy in a single line for each case. (-1 if no such strategy)

Sample Input

4 4
....
..*@
..*@
.X*@

6 6
...#@.
@..*..
#*##..
..##*#
..X...
[email protected]#...

Sample Output

7
11

题意：

推箱子小游戏，对应的给定一个人的位置信息和三个箱子以及三个洞的信息

‘#’表示 对应的墙壁

‘.’表示对应的空地  

‘X’表示人的位置

‘*’表示箱子的位置

‘@’表示箱子的目的地

思路：

爆搜，bfs ，对应的要维护一个包含一个人的信息以及三个箱子的位置信息

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
int N,M;
char map[9][9];
bool Hash[9][9][9][9][9][9][9][9];
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

struct node{
	int y,x;
};

struct state{
	node P,box[3];
	int step;
	bool is_ok(){
		return (0<=P.x && P.x<M 
		&& 0<=P.y && P.y<N && map[P.y][P.x]!='#');
	}
}a,b;

bool find(state cur){
	int num = 0;
	for(int i=0;i<3;i++){
		if(map[cur.box[i].y][cur.box[i].x] != '@') break;
		num++; 
	}
	return num == 3;
}
bool can_go(state cur,int y,int x,int box_id){
	
	for(int i=0;i<3;i++){
		if(cur.box[i].y == y &&  cur.box[i].x == x && i!= box_id) return false; 
	}
	return (map[y][x]!= '#' && 0<=y && y<N && 0<=x && x<M );
}

bool gethash(state cur){
	return Hash[cur.P.y][cur.P.x][cur.box[0].y][cur.box[0].x][cur.box[1].y][cur.box[1].x][cur.box[2].y][cur.box[2].x];
}

void sethash(state cur){
	Hash[cur.P.y][cur.P.x][cur.box[0].y][cur.box[0].x][cur.box[1].y][cur.box[1].x][cur.box[2].y][cur.box[2].x] = true;
}


int is_box(state cur){
	for(int i=0;i<3;i++){
		if(cur.P.y == cur.box[i].y && cur.P.x == cur.box[i].x  ) return i;
	}
	return -1;
}

int bfs(){
	a.step = 0;
	queue<state> que;
	que.push(a);
	
	while(!que.empty()){
		a = que.front(); que.pop();
		if(find(a)) return a.step;
		
		for(int i=0;i<4;i++){
			b = a;
			b.P.y = a.P.y + dy[i];
			b.P.x = a.P.x + dx[i]; 
			b.step = a.step +1;
			
			if(!b.is_ok()) continue;
			
			int box_id = is_box(b);
			if(box_id !=-1) {
				int x1 = b.P.x + dx[i];
				int y1 = b.P.y + dy[i];
				if(can_go(b,y1,x1,box_id)){
					b.box[box_id].y = y1;
					b.box[box_id].x = x1;
					if(!gethash(b)){
						sethash(b);
						que.push(b);
					}
				}
			}else{
				if(!gethash(b)){
					sethash(b);
					que.push(b);
				}
			} 
		}		
	}
	return -1;
}
int main(){
	
	while(scanf("%d%d",&N,&M)!=EOF){
		int cur =0;
		for(int i=0;i<N;i++){
			scanf("%s",map[i]);
			for(int j=0;j<M;j++){
				if(map[i][j] == 'X'){
					a.P.y = i; a.P.x = j;
				}else if(map[i][j] == '*'){
					a.box[cur].y = i; a.box[cur++].x = j; 
				}
			}
		}
		sethash(a);
		memset(Hash,0,sizeof(Hash));
		int res = bfs();
		printf("%d\n",res);
		
	}
	
	return 0;
}