04129: 变换的迷宫
bfs, http://cs101.openjudge.cn/practice/04129
你现在身处一个R*C 的迷宫中，你的位置用"S" 表示，迷宫的出口用"E" 表示。
迷宫中有一些石头，用"#" 表示，还有一些可以随意走动的区域，用"." 表示。
初始时间为0 时，你站在地图中标记为"S" 的位置上。你每移动一步（向上下左右方向移动）会花费一个单位时间。你必须一直保持移动，不能停留在原地不走。
当前时间是K 的倍数时，迷宫中的石头就会消失，此时你可以走到这些位置上。在其余的时间里，你不能走到石头所在的位置。
求你从初始位置走到迷宫出口最少需要花费多少个单位时间。
如果无法走到出口，则输出"Oop!"。
输入
第一行是一个正整数 T，表示有 T 组数据。 每组数据的第一行包含三个用空格分开的正整数，分别为 R、C、K。 接下来的 R 行中，每行包含了 C 个字符，分别可能是 "S"、"E"、"#" 或 "."。 其中，0 < T <= 20，0 < R, C <= 100，2 <= K <= 10。
输出
对于每组数据，如果能够走到迷宫的出口，则输出一个正整数，表示最少需要花费的单位时间，否则输出 "Oop!"。
样例输入
1
6 6 2
...S..
...#..
.#....
...#..
...#..
..#E#.样例输出
7Below is a Python implementation that solves the problem in
import sys
from collections import deque
def solve():
input = sys.stdin.readline
T = int(input())
for _ in range(T):
R, C, K = map(int, input().split())
maze = [list(input().rstrip('\n')) for _ in range(R)]
# Find S and E
for i in range(R):
for j in range(C):
if maze[i][j] == 'S':
sr, sc = i, j
elif maze[i][j] == 'E':
er, ec = i, j
# dist[r][c][m] = minimum absolute time to reach (r,c) with time mod K == m
INF = 10**18
dist = [[[INF]*K for _ in range(C)] for __ in range(R)]
dq = deque()
dist[sr][sc][0] = 0
dq.append((sr, sc, 0)) # at time 0
ans = None
while dq:
r, c, m = dq.popleft()
t = dist[r][c][m]
# If we've reached the exit, record and break (BFS ensures minimal time)
if (r, c) == (er, ec):
ans = t
break
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r+dr, c+dc
nt = t + 1
nm = nt % K
if not (0 <= nr < R and 0 <= nc < C):
continue
cell = maze[nr][nc]
# If it's a rock, only allowed if nt % K == 0
if cell == '#' and nm != 0:
continue
# '.' or 'S' or 'E' always ok
if dist[nr][nc][nm] > nt:
dist[nr][nc][nm] = nt
dq.append((nr, nc, nm))
if ans is None:
print("Oop!")
else:
print(ans)
if __name__ == "__main__":
solve()说明
状态定义
我们把每个位置的状态拆成 个子状态，对应「当前时间模 (K) 的值」。 转移条件
- 从
可以移动到上下左右的 ，所需时间加 1，得到新的时间 ，新的模数 。 - 如果目标格是 “#” 石头，则只有当
（即 恰好是 的倍数）时才允许进入。 - 其他格（“.”、“S”、“E”）则随时可走。
- 从
最短路
由于每一步代价均为 1，且我们用 BFS（双端队列）按层次遍历，首次到达出口 ((er,ec)) 的时间即为最少时间。复杂度
状态数为，每个状态处理四个方向，整体复杂度 ，对于 、 足够高效。
这样就可以正确地输出最少移动时间，若无法到达出口则输出 "Oop!"。
在不同的时间访问同一个地点的意义不同，但是在模k相同的时间访问同一个地点的意义是一样的。
容易想到广搜，但是数据大，会超时，需要剪枝。由于每过k单位时间，石头就会消失一次，那么当我们站在某点 (x,y) 时，时间为 t+k 和 t 时，它们之后行走面临的情境是完全一样的，那就意味着，对于某个状态的时间，我们可以取模后作为 visited[x][y][time] 的第三个变量，如果取模后的值代入发现已经访问过，那说明之前已经有更优越的情况出现过，不必再继续搜索了。
起点、终点可以当空地。用三维数组。
由于石头时有时无，所以应当允许重复到达相同位置(比如和终点之间只隔了个石头但是暂时过不去，在那里来回逛等到石头没了直接过去就可能比绕路省时)，但是如果真的无解会导致q里一直有元素，程序结束不了，所以考虑用
visited记录每次到达时的时间，如果在K的整数倍之前到过这里，情况就与之前重复，所以不允许再去，这样就处理了无解的情况。用 visited记录每次到达时的时间，取模，如果在K的整数倍之前到过这里，情况就与之前重复
import heapq
from math import inf
# 四个基本方向：右、下、左、上
DIRECTIONS = [(0, 1), (1, 0), (-1, 0), (0, -1)]
def find_shortest_path(grid, start, end, dimensions, cycle_length):
"""
寻找从起点到终点的最短路径。
:param grid: 地图信息（0为空地，1为石头）
:param start: 起点坐标 (x, y)
:param end: 终点坐标 (x, y)
:param dimensions: 地图尺寸 (rows, cols)
:param cycle_length: 穿过石头的时间周期
:return: 最短时间或 "Oop!" 表示无法到达
"""
rows, cols = dimensions
visited = [[[False] * cols for _ in range(rows)] for _ in range(cycle_length)]
priority_queue = [(0,) + start] # 初始时间为0加上起点坐标
while priority_queue:
time, x, y = heapq.heappop(priority_queue)
if (x, y) == end: # 到达终点
return time
for dx, dy in DIRECTIONS:
nx, ny = x + dx, y + dy
new_time = time + 1
if not (0 <= nx < rows and 0 <= ny < cols): # 检查是否在地图内
continue
if grid[nx][ny] == 1 and new_time % cycle_length == 0 and not visited[new_time % cycle_length][nx][ny]: # 穿石头
visited[new_time % cycle_length][nx][ny] = True
heapq.heappush(priority_queue, (new_time, nx, ny))
elif grid[nx][ny] == 0 and not visited[new_time % cycle_length][nx][ny]: # 普通空地
visited[new_time % cycle_length][nx][ny] = True
heapq.heappush(priority_queue, (new_time, nx, ny))
return "Oop!"
def main():
test_cases = int(input())
results = []
for _ in range(test_cases):
rows, cols, cycle_length = map(int, input().split())
grid = []
start = None
end = None
for i in range(rows):
line = input()
row = []
for j, char in enumerate(line):
if char == "S":
start = (i, j)
row.append(0) # 起点当空地
elif char == "E":
end = (i, j)
row.append(0) # 终点当空地
elif char == "#":
row.append(1) # 石头
else:
row.append(0) # 空地
grid.append(row)
result = find_shortest_path(grid, start, end, (rows, cols), cycle_length)
results.append(result)
for result in results:
print(result)
if __name__ == "__main__":
main()思路：模版bfs的变化
关键是要注意到每间隔周期到达同一个地方是等价的，只需要将到达这个地方余数为0-T-1的路径加入队列，也可以建三元的集合来判断。注意time的关系细节，⚠️#注意如果漏了可以=‘S’的情况会报错，可以回到起点再出发！！！
# 黄鹤鸣、24光华管理学院
# 我的题解，反思此处用集合set（）更完美？
from collections import deque
def bfs(matrix, n, m, k, start, end):
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
queue = deque([(start[0], start[1], 0)])
visited = [[[-1] * k for _ in range(m)] for _ in range(n)]
visited[start[0]][start[1]][0] = 0
while queue:
x, y, time = queue.popleft()
if (x, y) == end:
return time
for dx, dy in directions:
cx, cy = x + dx, y + dy
if 0 <= cx < n and 0 <= cy < m and visited[cx][cy][(time + 1) % k] == -1:
if (time + 1) % k == 0: # 注意⚠️这里是time+1
visited[cx][cy][(time + 1) % k] = 0
queue.append((cx, cy, time + 1))
else:
# 注意⚠️此处如果漏了可以=‘S’的情况会报错
if matrix[cx][cy] != '#':
visited[cx][cy][(time + 1) % k] = 0
queue.append((cx, cy, time + 1))
return 'Oop!'
for _ in range(int(input())):
R, C, K = map(int, input().split())
board = [input() for _ in range(R)]
start = None
end = None
for i in range(R):
for j in range(C):
if board[i][j] == 'S':
start = (i, j)
if board[i][j] == 'E':
end = (i, j)
print(bfs(board, R, C, K, start, end))# 三维visited。蒋子轩 23工学院
from collections import deque
def bfs(x, y):
visited = {(0, x, y)}
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
queue = deque([(0, x, y)])
while queue:
time, x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
temp = (time + 1) % k
if 0 <= nx < r and 0 <= ny < c and (temp, nx, ny) not in visited:
cur = maze[nx][ny]
if cur == 'E':
return time + 1
elif cur != '#' or temp == 0:
queue.append((time + 1, nx, ny))
visited.add((temp, nx, ny))
return 'Oop!'
t = int(input())
for _ in range(t):
r, c, k = map(int, input().split())
maze = [list(input()) for _ in range(r)]
for i in range(r):
for j in range(c):
if maze[i][j] == 'S':
print(bfs(i, j))from collections import deque
# 优化初始化函数
arr2 = lambda m, n: [[' ' for _ in range(n)] for _ in range(m)]
arr3 = lambda m, n, l: [[[False for _ in range(l)] for _ in range(n)] for _ in range(m)]
N = 100
K = 10
class Node:
def __init__(self, r=0, c=0, t=0):
self.row = r
self.col = c
self.time = t
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
data = input().split()
def solve():
idx = 0
t = int(data[idx])
idx += 1
for _ in range(t):
r, c, k = map(int, input().split())
idx += 3
maze = arr2(r, c)
vis = arr3(r, c, k)
q = deque()
for i in range(r):
maze[i] = list(input())
start_nodes = []
end_pos = None
for i in range(r):
for j in range(c):
if maze[i][j] == 'S':
start_nodes.append(Node(i, j))
vis[i][j][0] = True
elif maze[i][j] == 'E':
end_pos = (i, j)
while q or start_nodes:
if start_nodes:
q.extend(start_nodes)
start_nodes.clear()
node = q.popleft()
if node.row == end_pos[0] and node.col == end_pos[1]:
print(node.time)
break
for i in range(4):
nrow = node.row + dr[i]
ncol = node.col + dc[i]
if nrow < 0 or nrow >= r or ncol < 0 or ncol >= c:
continue
new_time = (node.time + 1) % k
if vis[nrow][ncol][new_time]:
continue
if new_time != 0 and maze[nrow][ncol] == '#':
continue
vis[nrow][ncol][new_time] = True
q.append(Node(nrow, ncol, node.time + 1))
if not q:
print("Oop!")
solve()arr2 = lambda m,n : [ [' ' for j in range(n)] for i in range(m) ]
arr3 = lambda m,n,l : [ [ [False for k in range(l)] for j in range(n)] for i in range(m) ]
N = 100
K = 10
class Node:
def __init__(self, r=0, c=0, t=0):
self.row = r
self.col = c
self.time = t
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
for _ in range(int(input())):
maze = arr2(N, N) # 注意不同数据组之间的初始化
vis = arr3(N, N, K)
q = []
r,c,k = map(int, input().split())
for i in range(r):
maze[i][:c] = list(input())
tr = tc = cnt = 0;
for i in range(r):
for j in range(c):
if maze[i][j] == 'S':
q.append(Node(i, j))
vis[i][j][0] = True
cnt += 1
if cnt == 2: break
elif maze[i][j] == 'E':
tr = i
tc = j
cnt += 1
if cnt == 2: break
while(len(q)):
t = q[0] # t : Node
if t.row == tr and t.col == tc: break
q.pop(0)
for i in range(4):
nrow = t.row + dr[i]
ncol = t.col + dc[i]
if nrow < 0 or nrow >= r or ncol < 0 or ncol >= c:
continue
# 剪枝很容易能知道，由于每过k单位时间，石头就会消失一次，那么当我们站在某点 (x,y) 时，
# 时间为 t+k 和 t 时，它们之后行走面临的情境是完全一样的，那就意味着，
# 对于某个状态的时间，我们可以取模后作为 visited[x][y][time] 的第三个变量，
# 如果取模后的值代入发现已经访问过，那说明之前已经有更优越的情况出现过，不必再继续搜索了.
if vis[nrow][ncol][(t.time + 1) % k]:
continue
# 时间是K 的倍数时，迷宫中的石头就会消失
if (t.time + 1) % k and maze[nrow][ncol] == '#':
continue;
vis[nrow][ncol][(t.time + 1) % k] = True
q.append(Node(nrow, ncol, t.time + 1))
if len(q) == 0:
print("Oop!")
else:
print(q[0].time)首先易得：对于由正方形网格上的点组成的闭合环路周长必定为偶数个正方形边长 推论：对于地图上任意一点，不存在两条长度奇偶性不同的路径；即到达某点的所有路径奇偶性相同 又：对于第t步，只要其周围存在点不是墙，就可以在两点中反复横跳在该点达到第t+2n步 故：若存在n，使得t+2n+1 = mK，则该点可进入该墙 @1 我们将上述过程抽象为一步考虑进 一个点可到达的点 则不过是在传统Dijkstra中加入一些路径而已 所以本法与其它方法不同，只需2维Visited即可，也不会重复遍历某点，时间与空间上均较优（地图较大时尤为显著） 94ms 3916kB 注意：在实现@1的判断时注意一些边界条件，否则容易犯逻辑错误
# 姜歆宇 元培
import heapq
from math import inf
directions = [(1,0),(0,1),(-1,0),(0,-1)]
def check(x,y,s):
if M[x][y] == 1: #本来就在墙上当然不能再进入其它墙
return False
if k == 2 and s != 0: #这样不会被四面围堵（除非在原点）
return True
for dx,dy in directions: #被四面围堵就不能反复横跳了
if 0 <= (nx:=x+dx) < a and 0 <= (ny:=y+dy) < b and M[nx][ny] == 0:
return True
return False
def best_way(points):
while points:
s,x,y = heapq.heappop(points)
if x == ex and y == ey:
return s
for dx,dy in directions:
if 0 <= (nx:=x+dx) < a and 0 <= (ny:=y+dy) < b:
if M[nx][ny] == 1 and check(x,y,s):
if S[nx][ny] > (ns:=(1+s//k)*k) and s%2 != ns%2: #奇偶性不同故可以穿
S[nx][ny] = ns
if not C[nx][ny]:
heapq.heappush(points,(ns,nx,ny))
C[nx][ny] = True
elif S[nx][ny] > (ns:=ns+k) and s%2 != ns%2: #注意k为奇数时k与2k奇偶性不同
S[nx][ny] = ns
if not C[nx][ny]:
heapq.heappush(points,(ns,nx,ny))
C[nx][ny] = True
elif M[nx][ny] == 0 and S[nx][ny] > (ns:=s+1):
S[nx][ny] = ns
if not C[nx][ny]:
heapq.heappush(points,(ns,nx,ny))
C[nx][ny] = True
return "Oop!"
Ans = []
T = int(input())
for t in range(T):
a,b,k = map(int,input().split())
M = [[0]*b for _ in range(a)]
for i in range(a):
l = input()
for j in range(b):
if l[j] == 'S':
sx,sy = i,j
elif l[j] == 'E':
ex,ey = i,j
elif l[j] == '#':
M[i][j] = 1
S = [[inf]*b for _ in range(a)]
S[sx][sy] = 0
C = [[False]*b for _ in range(a)]
C[sx][sy] = True
Ans.append(best_way([(0,sx,sy)]))
for ans in Ans:
print(ans)难得有一次想写代码的思路了，毕竟难得想出与众不同的优性能算法，希望会加入题解里 但是用时还是太长了，有想法但思路不严谨debug困难是这样的 希望期末不会死在debug上（还是要吐槽OJ没有测试数据，这次变换的迷宫是自己写的随机生成器刷了几十条数据才找出bug
import random
T = random.randint(4,6)
print(T)
for t in range(T):
R = random.randint(2,100)
C = random.randint(2,100)
K = random.randint(2,20)
print(f'{R} {C} {K}')
l = ['.','#','.','.','#']
M = [[0]*C for _ in range(R)]
for i in range(R):
for j in range(C):
M[i][j] = random.choice(l)
M[0][0] = 'S'
M[-1][-1] = 'E'
for i in range(R):
print(''.join(M[i]))1 59 75 2 S.#.....#.#..##......#.###.##.#...#.###..#.##.##.##...#...#.....##..###.... .#####...#.#.......#..#.###.#.....#.#.##.#....#..##.###........#.#..#...#.# .####.#.###...#.....#..#.###..###.#..#####.#.#..##.###..##.#.#.....#.#.#... .#....#.##..##..#..#....#.###.#.##..#......#..#.#.....#....##...####.....#. ..##.#...#.#.#....#....#.###.#.##....#..#.###..#.#....#.####.....#.##.###.. #.#...###..##....#..#......#..#.#.##..##..#.##...#.....#......#.#####...#.# .####..#..##..###.###...##.#....#.##.##...###....#..#.#...##..#.#.#.#.#.#.. ....#..#.............###...#####..#..#..###.......####..#..##...####.....#. .#...##..#.##.#.#.#..###..#..##.###....###....#.......##.##.#.##...###...#. .##.....##.#.#..#.#.#.......##..#.#.####..#...#........#....#...#.#.....#.. ##..#.##.##.....#.#.##.##......##..#.#.##...#.#..###...#......##..#....#.## #..#..##..#..####...##.##....#.#..#...######...#.#.#........##.#..#...#.#.# .##.#....#..#.#.#..#.####..##..##...#....###.#.#.#.###....##....#...##.#.#. .#.###....#....#....#....##..#.###.#...#....#.###.#..#.#.....##.####..#.#.. ..###....#.##..###.#..#..#...#.#.....##.#.#..#.#..#.##.##.#.######....#.... ......#........##.###..#.#..#..#.#.##.#.......###...##..#.##...####....#... #.#..#...######..###.##...#.#..###......#.#.#.#.##.######..#..#.....#....#. .#..####.#...#....#...#.#.....#.#####...#...#.....#..##.....#.........##... .###.##.######.#........#.##...#.##.###...#.##..##...#.##..#....#...#.#..#. #.#.#.#.##..#...##....#.#.....#...#.........#.#.#...#.##..#..#..........#.# ###..####....#..##....#.#.#.######...###..#.##.#.#..............##...#..#.. ##.####.####.##.#.##............#.#.......#....##..#.###..#...#...##..##.#. ####.......##...##..#..........###.#..##..###.#...##...#........#....#.#..# ......#....##..###...##..##.#...#.#.##......###...#.######.#.#.#..#..###... ......##.#####...#.####.###....#.##.#.#......#..#..#........####..##.#..... .##..##..#.##...#...#..##..#..###.#..##.##..#....#...#.#..#..#.####.#.#.### .#..#.#..#.##....##..#...#..##....####...###.#..##.....#......#..#..###.#.. .#.....##..##..#.##.#.##...##.##...##..#.######.##...#.#..#......#.#...##.. ..##..#...####..###..#..#.#.#..#.##.#..##..####.#...###..##..#.##.....#.#.. ..######...#..###..######.###..####..#......###.#.....#.###..######.#.#.... ....##.####.##..##..##..##...#.......#.#....#..##.#..#.#.#..#.##.##..##.#.. #.##....#..##.##.#...#.##..###......#....####...####....#..#.....##..#..### ##.#...#....#..#..#.#.#####......###...#.#..#..#..##.#.#..#...#..#..#...... .###.#.##......##.#.####.##..#.#..##.##.#..#.#..#.....###.#...#..#.#..#.... ......#.###..#.#..#.#.#..#..#.##..#..##.......####......#........#......#.# ...#.....##...#.#....#..##.#........#..##....#..#....#....###....#.#.#....# ....#.#..###.#####.######.#...##.####....##.#.###.#..#.#..#..##..##.......# .....##..#..##.#.....##...#..#.##.....####..####.#.#..#..........#.....#.## ##.....#.##.#..#..###.#....##..###...##....###.....#.#.#..###..#.#...#...#. ..#.#.#..##.......#.##.#..#.##.#....##...###.###.#..#......#.....#...##...# ..#.....##.###.##.#...#...#..#.#.......#...#..#######..#..#...##.###.##.##. #.###.#.....#..###..#...##.#.#...##.#..#.##..#...#.####....#.#..#####...... ##.....#.#.##.........#.##.#.#.#.#...#..#.#...#..#.#.....#.##.##...#..#.##. #.#..#.#..#...###.#.###.#.####.#.###.#.#####..##...##..#.##..#.#..#.#..#.#. .#.#.#.###..........#..#..###......####..####.##..#...##.#.##...####...##.# .##...#...#......##...#.##.##.#..##...###..#########.##..##.####...#.#.##.. ##.##...........#..#..#.##...#..#.##..#..#.#......###.#.#####.#...#...#.#.. #.##.##.#..#...###...#.#.#.##....###...#.#.#.#.#.##..#..#####.#.#.........# #.##...#####...#...###..##.##..#.#.#..####.#.##.#..##.####.......#..#...#.. .###.######.....######.##.#.#.#..#......##.#...#.#.....#.....######...##..# ......#.#.#.#####..###.###....##.#.#....#......##.......#.##...#..####....# #.#...#......###..#......#..###.#..#..#..#.#.....#......#..#.#..##...##.... .#.#.#......#..##.#..#.##.#.#.#.....#......#.#.##.....#....#..#.#.#.....#.# #.#..#..#.#.##..##.#..##..#...###..#.####...#.#.....####......####......#.# #...#.....#.#.......##...##.###.#..#.##...#######.##...#....#...##........# .#.##...##...#...#.#.#....##...##.#..#...#....#..#.#...#......#.##.####.##. ....#..#...#....#.###..#.#.#.##.###...#...#.#..#.##.#...###.###..##...##.#. ..#..#...#...#...#....#..#...#.#..###....####..#...#.#.#.###.........#...#. ....#.#..#.##..#.#..##.......#..#.#.#...#.....#..#...####..#..#.#....#....E 这组数据才发现是k=2导致bug
【昂奕, 24化学与分子工程学院】
思路：Dijkstra,但是有一些问题:
探路探到石头的时候，如果由最短路径走到一块可能未消失的石头上的时间(w+1)通过若干次加二可以得到k的整数倍，就说明可以在石头旁边徘徊来等到它消失然后走上去。 如果可以走上去，就入队并更新相应的时间，如果不行，就不入队 走上去的条件可以证明为not (w%2==0 and k%2==0) 但是如果某个'.'或者四面被石头包围，就不能这样徘徊，得单独考虑。 对于一般的'.',不能入队的条件是k>2 and 四面包围 对于S，不能入队(也就是开场就死)的条件是四面包围 对于E，它即使被包围也得入队,不然就走不到了，入队了也没关系,反正走到它就返回了
特别鸣谢:元培 姜歆宇,没有他的编测试数据的程序,我这题通宵都AC不了(哭)。
import heapq
MAXN=float('inf')
def dead(x0,y0):
return mat[x0-1][y0]==mat[x0][y0-1]==mat[x0+1][y0]==mat[x0][y0+1]=='#' and mat[x0][y0]=='.' and k>2
def dij(s,mat):
global k
weight=[[MAXN]*len(mat[0]) for __ in range(len(mat))]
q=[s]
weight[s[1]][s[2]]=0
d=[(-1,0),(1,0),(0,-1),(0,1)]
while q:
w,x,y=heapq.heappop(q)
#print((w,x,y))
if mat[x][y]=='E':
return w
for dx,dy in d:
nx,ny=x+dx,y+dy
if 1<=nx<len(mat)-1 and 1<=ny<len(mat[0])-1 :
if mat[nx][ny] in {'.','E','S'} and weight[nx][ny]>w+1 and not dead(nx,ny):
weight[nx][ny]=w+1
heapq.heappush(q,(w+1,nx,ny))
elif mat[nx][ny]=='#' and not(w%2==0 and k%2==0) and mat[x][y]!='#':
tmp=w+1#找到到这个#的最短路径长
while tmp%k!=0:
tmp+=2
if weight[nx][ny]>tmp:#更新最短路径,入队
weight[nx][ny]=tmp
heapq.heappush(q,(tmp,nx,ny))
return 'Oop!'
t=int(input())
for _ in range(t):
n,m,k=map(int,input().split())
mat=['#'*(m+2)]
s,x0,y0=(),0,0
for i in range(n):
mat.append(['#']+list(input())+['#'])
if 'S' in mat[i]:
x0,y0=i,mat[i].index('S')
s=(0,x0,y0)
mat.append(['#']*(m+2))
#for _ in mat:
# print(*_)
if mat[x0-1][y0]==mat[x0][y0-1]==mat[x0+1][y0]==mat[x0][y0+1]=='#':
print('Oop!')
else:
print(dij(s,mat))