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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;

int t,r,c;
int sx,sy,tx,ty;
char m[210][210] = {0};

struct _node {
    int x,y;
    int step;
};

_node node[210*210];
int head = 0,tail =0;

void push(int x,int y,int s){
    node[tail].x = x;
    node[tail].y = y;
    node[tail].step = s;
    tail++;
}

void pop(){
    head++;
}

bool empty(){
    return tail == head;
}

int fx[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} };

bool vis[210][210] = {0};

bool in_map(int x,int y){
    if( x>= 1 && x <= r && y>=1 && y <=c)
        return true;
    return false;
}
void bfs(){
    head = 0; tail = 0;
    memset(vis,0,sizeof(vis));
    //加入起点
    push(sx,sy,0);

    while( empty() == false){
        
        int x = node[head].x;
        int y = node[head].y;
        int s = node[head].step;
        pop();

        int i;
        for(i=0;i<4;i++){
            int nx = x + fx[i][0];
            int ny = y + fx[i][1];
            
            if( nx == tx && ny == ty){
                cout << s+1 << endl;
                return;
            }


            if(in_map(nx,ny) && vis[nx][ny]==0 && m[nx][ny] == '.'){
                vis[nx][ny] = 1;
                push(nx,ny,s+1);
            }

        }
    }
    cout << "oop!" << endl;
}


int main(){
    cin >> t;
    
    int i,j,k;
    for(i=1;i<=t;i++){
        
        cin >> r >> c;
        for(k=1;k<=r;k++)
            for(j=1;j<=c;j++){
                cin >> m[k][j];
                if( m[k][j] == 'S'){
                    sx = k;
                    sy =j;
                }
                else if( m[k][j] == 'E'){
                    tx = k;
                    ty =j;
                }
            }
        bfs();
        
    }
    return 0;
}