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
| #include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N=200;
typedef pair<int, int> PII;
int n;
int r,c;
char maze[N][N];
int dist[N][N];
int bfs(PII start)
{
queue<PII> q;
q.push(start);
memset(dist,-1,sizeof(dist));
dist[start.x][start.y]=0;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
while(q.size())
{
auto t=q.front();
q.pop();
res++;
for(int i=0;i<4;i++)
{
int x=t.x+dx[i],y=t.y+dy[i];
if (x >= 0 && x < r && y >= 0 && y < c && maze[x][y] != '#' && dist[x][y] == -1)
{
dist[x][y] = dist[t.x][t.y] + 1;
if (maze[x][y] == 'E')
return dist[x][y];
q.push({x, y});
}
}
}
return -1;
}
int main()
{
cin>>n;
while(n)
{
cin>>r>>c;
int x,y;
PII start;
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
{
cin>>maze[i][j];
if(maze[i][j]=='S') start={i,j};
}
int ans=bfs(start);
if(ans!=-1)
cout<<ans<<endl;
else
cout<<"oop!"<<endl;
n--;
}
}
|