﻿HDU 1254 推箱子(BFS+BFS)-Ocrosoft

# 推箱子

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7107    Accepted Submission(s): 2024

Problem Description

Input

Output

Sample Input
```
1
5 5
0 3 0 0 0
1 0 1 4 0
0 0 1 0 0
1 0 2 0 0
0 0 0 0 0

```

Sample Output
```
4

```

Solution

```#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
int n,m;
int mp[10][10];
bool reach[10][10];
bool vis[10][10][10][10];
int dir[4][2]= {0,1,0,-1,1,0,-1,0};
struct Point
{
int x,y;
int step;
bool check()
{
if(x<0||y<0||x>=n||y>=m)return 0;
if(mp[x][y]!=0)return 0;
if(reach[x][y])return 0;
return 1;
}
bool check_b(Point p)
{
if(x<0||y<0||x>=n||y>=m)return 0;
if(mp[x][y]!=0)return 0;
if(vis[x][y][p.x][p.y])return 0;
return 1;
}
} p,e,b; //person,end,box
void bfs_p()
{
queue<Point> q;
ms(reach);
q.push(p);
Point t,tt;
while(!q.empty())
{
t=q.front();
q.pop();
reach[t.x][t.y]=1;
for(int i=0; i<4; i++)
{
tt.x=t.x+dir[i][0];
tt.y=t.y+dir[i][1];
if(tt.check())q.push(tt);
}
}
}
int bfs_b()
{
ms(vis);
queue<Point> q;
q.push(b);
q.push(p);
Point t,tt;
while(!q.empty())
{
t=q.front();
q.pop();
p=q.front();
q.pop();
if(t.x==e.x&&t.y==e.y)return t.step;
vis[t.x][t.y][p.x][p.y]=1;
mp[t.x][t.y]=2;
bfs_p();
mp[t.x][t.y]=0;
for(int i=0; i<4; i++)
{
tt.x=t.x+dir[i][0];
tt.y=t.y+dir[i][1];
tt.step=t.step+1;
if(tt.check_b(t)&&reach[t.x-dir[i][0]][t.y-dir[i][1]])
{
q.push(tt);
q.push(t);
}
}
}
return -1;
}
int main()
{
int N;
cin>>N;
while(N--)
{
cin>>n>>m;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
{
cin>>mp[i][j];
if(mp[i][j]==2)
b.x=i,b.y=j,b.step=0;
else if(mp[i][j]==3)
e.x=i,e.y=j,mp[i][j]=0;
else if(mp[i][j]==4)
p.x=i,p.y=j,mp[i][j]=0;
}
printf("%d\n",bfs_b());
}
return 0;
}
```