HDU/HDOJ 1254プッシュボックスネストの広さ優先検索

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1254
考え方:まず人が箱の進むところの反対方向に到達できるかどうかを判断し、最初のbfs 1で、箱が目標点に到達できるかどうかを判断します.これは主bfsです.箱は一歩歩くたびにbfs 1を呼び出します.箱は4つの方向から押し出され、3次元配列を開いて各点の4つの方向の状態マークを表します.上から下へ足を下ろすことができるからです.下から元の場所に戻すこともできますので、2 Dタグは満たされません.
ACコード:0 MS 360 k

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <fstream>
#include <queue>
using namespace std;
struct node1{
	int x,y;
};
node1 a,b,c;
struct Node{
	node1 box,man;
	int step;
}p,q;
queue<node1> Q1;
queue<Node> Q2;
bool visitman[7][7],visitbox[10][10][4];
int maze[10][10];
int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};//shang， ，xia，  
int m,n,endx,endy;
bool isbond(node1 &a){
	if(a.x<0 || a.x>=m || a.y<0 || a.y>=n || maze[a.x][a.y]==1)return 1;
	return 0;
}
bool bfs1()
{
	while(!Q1.empty())Q1.pop();


	memset(visitman,0,sizeof(visitman));
	
	Q1.push(p.man);       //2,1 
	
	
	visitman[p.man.x][p.man.y]=1;//2.1 
	visitman[p.box.x][p.box.y]=1;//3.1
	while(!Q1.empty())
	{
		b=Q1.front();
		Q1.pop();
		
		
		if(b.x==a.x && b.y==a.y)return 1; //a:4.1
		for(int i=0;i<4;i++)   // ， ， ，  
		{
			c.x=b.x+dir[i][0];
			c.y=b.y+dir[i][1];
			
		//	cout<<"before:  "<<c.x<<" "<<c.y<<endl;
		//	cout<<visitman[c.x][c.y]<<endl;
		//	cout<<isbond(c)<<endl;
			
			if(isbond(c))continue;	
		//	if(visitman[c.x][c.y])continue;
			if(visitman[c.x][c.y])continue;
			
		//	cout<<"after: "<<c.x<<" "<<c.y<<endl; 
			visitman[c.x][c.y]=1;
			
			Q1.push(c);
			
		} 
		
	}
	return 0;
}
int bfs()
{
	while(!Q2.empty())
	{
		p=Q2.front();
		Q2.pop();
		
		
		if(p.box.x==endx&&p.box.y==endy)return p.step;
		
		for(int i=0;i<4;i++)
		{
			q.box.x=p.box.x+dir[i][0];
			q.box.y=p.box.y+dir[i][1];
			if(isbond(q.box))continue;
			if(visitbox[q.box.x][q.box.y][i])continue;
			 
		
			a.x=p.box.x-dir[i][0];   //    ：            ，  --- 
			a.y=p.box.y-dir[i][1];   //----            
			
		
			
			if(isbond(a))continue;  //            
			
	
			if(!bfs1())continue; //          
		
			q.man=p.box;
			visitbox[q.box.x][q.box.y][i]=1;
			q.step=p.step+1;
			Q2.push(q); 
		}
	}
	return -1;
}
int main()
{
	//ifstream fin;
	//fin.open("data1.txt");
	int t;
	cin>>t;
	while(t--)
	{
		cin>>m>>n;
		for(int i=0;i<m;i++){
			for(int j=0;j<n;j++){
				cin>>maze[i][j];
				if(maze[i][j]==2){
					p.box.x=i;
					p.box.y=j;
				}
				if(maze[i][j]==3){
					endx=i;
					endy=j;
				}
				if(maze[i][j]==4){
					p.man.x=i;
					p.man.y=j;
				}
			}
		}
		memset(visitbox,0,sizeof(visitbox));
		while(!Q2.empty())Q2.pop();
		p.step=0;
		Q2.push(p);
		cout<<bfs()<<endl;
	}
	
	return 0;

}