1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<iostream>
#include<cstring>
#include<queue>
#define MAX 200+5
using namespace std;
struct node
{
int x, y;
};
char maze[MAX][MAX + 1] = { 0 };
bool visit[MAX][MAX + 1] = { false };
int step[MAX][MAX + 1] = { 0 };
int dir[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
int sx, sy, ex, ey;
int N, M;
queue <node> que;
void BFS(int x, int y)
{
node q;
q.x = x; q.y = y;
que.push(q);
while (!que.empty())
{
node now = que.front();
node next;
que.pop();
for (int i = 0; i<4; i++)
{
next.x = now.x + dir[i][0];
next.y = now.y + dir[i][1];
if (next.x >= 0 && next.x< N && next.y >= 0 && next.y< M && maze[next.x][next.y] != '#' && visit[next.x][next.y] == false)
{
visit[next.x][next.y] = true;
step[next.x][next.y] = step[now.x][now.y] + 1;
que.push(next);
}
}
}
}
int main()
{
int t;
cin >> t;
while(t--)
{
while(cin >>N >> M)
{
memset(maze,0,sizeof(maze));
memset(step,0,sizeof(step));
memset(visit,false,sizeof(visit));
for (int i = 0; i<N; i++)
for (int j = 0; j<M; j++)
{
cin >> maze[i][j];
if (maze[i][j]=='p')
{
ex=i;ey=j;
}
}
for (int i = 0; i<N; i++)
for (int j = 0; j<M; j++)
{
if (maze[i][j] == 'm')
{
BFS(i,j);
if(step[ex][ey]!=0) cout << step[ex][ey] << endl;
else cout << "-1" << endl;
}
}
}
}
return 0;
}
|
