from collections import deque
# 四个方向的偏移量
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def is_valid(x, y, n, grid, visited):
"""
检查坐标是否合法：在范围内、不是墙、未访问过。
"""
return 0 <= x < n and 0 <= y < n and grid[x][y] != '#' and not visited[x][y]
def bfs(grid, n, start, target):
"""
使用 BFS 寻找最短路径。
"""
queue = deque([(*start, 0)]) # 队列存储 (x, y, 步数)
visited = [[False] * n for _ in range(n)]
visited[start[0]][start[1]] = True
while queue:
x, y, steps = queue.popleft()
# 如果到达目标点
if (x, y) == target:
return steps
# 尝试四个方向移动
for dx, dy in DIRECTIONS:
nx, ny = x + dx, y + dy
if is_valid(nx, ny, n, grid, visited):
visited[nx][ny] = True
queue.append((nx, ny, steps + 1))
return -1 # 如果找不到目标点
if __name__ == "__main__":
# 输入地图大小
n = int(input())
grid = []
start = target = None
# 输入地图并找到起点和终点
for i in range(n):
row = input().strip().split() # 按空格拆分输入行
grid.append(row)
for j in range(n):
if row[j] == 'S':
start = (i, j)
elif row[j] == 'T':
target = (i, j)
# 运行 BFS
result = bfs(grid, n, start, target)
print(result)
