Time Limit: 1000MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u

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

AC代码：

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int m, n, map[10][10];
bool vis[10][10][10][10];
const int dx[] = {0, 0, 1, -1},
dy[] = {1, -1, 0, 0};
struct node
{
int mx, my, bx, by, step;
};
struct pos
{
int x, y;
};
node start;
queue <node> q;
void input()
{
scanf("%d%d", &m, &n);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
scanf("%d", &map[i][j]);
if (map[i][j] == 2)
{
map[i][j] = 0;
start.bx = i;
start.by = j;
}
else if (map[i][j] == 4)
{
map[i][j] = 0;
start.mx = i;
start.my = j;
}
}
}
void pre()
{
while (!q.empty())
q.pop();
memset(vis, 0, sizeof(vis));
}
bool check(int x, int y)
{
if (x < 0 || x >= m || y < 0 || y >= n || map[x][y] == 1)
return 0;
return 1;
}
bool bfs_man(int sx, int sy, int ex, int ey, int bx, int by)
{
if (!check(sx, sy))
return 0;
queue <pos> qq;
bool vis2[10][10] = {0};
vis2[sx][sy] = vis2[bx][by] = 1;
qq.push((pos){sx, sy});
while (!qq.empty())
{
pos u = qq.front();
qq.pop();
if (u.x == ex && u.y == ey)
return 1;
pos next;
for (int i = 0; i < 4; i++)
{
next.x = u.x + dx[i];
next.y = u.y + dy[i];
if (!check(next.x, next.y) || vis2[next.x][next.y])
continue;
vis2[next.x][next.y] = 1;
qq.push(next);
}
}
return 0;
}
void bfs()
{
pre();
q.push(start);
vis[start.bx][start.by][start.mx][start.my] = 1;
while (!q.empty())
{
node u = q.front();
q.pop();
if (map[u.bx][u.by] == 3)
{
printf("%d\n", u.step);
return;
}
node next;
for (int i = 0; i < 4; i++)
{
next.bx = u.bx + dx[i];
next.by = u.by + dy[i];
next.mx = u.bx;
next.my = u.by;
next.step = u.step + 1;
if (!check(next.bx, next.by) || vis[next.bx][next.by][next.mx][next.my] || !bfs_man(u.mx, u.my, u.bx - dx[i], u.by - dy[i], u.bx, u.by))
continue;
vis[next.bx][next.by][next.mx][next.my] = 1;
q.push(next);
}
}
printf("-1\n");
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
input();
bfs();
}
return 0;
}