题解 | 地牢逃脱

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<string>& maze, int x0, int y0, vector<pair<int, int>>& moves) {
        int n = maze.size();
        int m = maze[0].size();
        vector<vector<int>> dist(n, vector<int>(m, -1));
        queue<pair<int, int>> q;
        
        // 初始化起点
        q.push({x0, y0});
        dist[x0][y0] = 0;
        
        // BFS遍历
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            
            // 尝试所有移动方式
            for (auto [dx, dy] : moves) {
                int nx = x + dx;
                int ny = y + dy;
                
                // 检查新位置是否合法
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                    maze[nx][ny] == '.' && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
        
        // 找出最大步数
        int maxDist = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (maze[i][j] == '.' && dist[i][j] == -1) {
                    return -1;  // 存在不可达的可通行位置
                }
                if (maze[i][j] == '.') {
                    maxDist = max(maxDist, dist[i][j]);
                }
            }
        }
        
        return maxDist;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<string> maze(n);
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
    }
    
    int x0, y0;
    cin >> x0 >> y0;
    
    int k;
    cin >> k;
    vector<pair<int, int>> moves(k);
    for (int i = 0; i < k; i++) {
        int dx, dy;
        cin >> dx >> dy;
        moves[i] = {dx, dy};
    }
    
    Solution solution;
    cout << solution.solve(maze, x0, y0, moves) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int solve(char[][] maze, int x0, int y0, int[][] moves) {
            int n = maze.length;
            int m = maze[0].length;
            int[][] dist = new int[n][m];
            Queue<int[]> q = new LinkedList<>();
            
            // 初始化距离数组
            for (int i = 0; i < n; i++) {
                Arrays.fill(dist[i], -1);
            }
            
            // 初始化起点
            q.offer(new int[]{x0, y0});
            dist[x0][y0] = 0;
            
            // BFS遍历
            while (!q.isEmpty()) {
                int[] curr = q.poll();
                int x = curr[0], y = curr[1];
                
                // 尝试所有移动方式
                for (int[] move : moves) {
                    int nx = x + move[0];
                    int ny = y + move[1];
                    
                    // 检查新位置是否合法
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                        maze[nx][ny] == '.' && dist[nx][ny] == -1) {
                        dist[nx][ny] = dist[x][y] + 1;
                        q.offer(new int[]{nx, ny});
                    }
                }
            }
            
            // 找出最大步数
            int maxDist = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (maze[i][j] == '.' && dist[i][j] == -1) {
                        return -1;  // 存在不可达的可通行位置
                    }
                    if (maze[i][j] == '.') {
                        maxDist = Math.max(maxDist, dist[i][j]);
                    }
                }
            }
            
            return maxDist;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        char[][] maze = new char[n][m];
        for (int i = 0; i < n; i++) {
            maze[i] = sc.next().toCharArray();
        }
        
        int x0 = sc.nextInt();
        int y0 = sc.nextInt();
        
        int k = sc.nextInt();
        int[][] moves = new int[k][2];
        for (int i = 0; i < k; i++) {
            moves[i][0] = sc.nextInt();
            moves[i][1] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.solve(maze, x0, y0, moves));
        
        sc.close();
    }
}

from collections import deque
from typing import List

class Solution:
    def solve(self, maze: List[str], x0: int, y0: int, moves: List[List[int]]) -> int:
        n, m = len(maze), len(maze[0])
        dist = [[-1] * m for _ in range(n)]
        q = deque([(x0, y0)])
        dist[x0][y0] = 0
        
        # BFS遍历
        while q:
            x, y = q.popleft()
            
            # 尝试所有移动方式
            for dx, dy in moves:
                nx, ny = x + dx, y + dy
                
                # 检查新位置是否合法
                if (0 <= nx < n and 0 <= ny < m and 
                    maze[nx][ny] == '.' and dist[nx][ny] == -1):
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
        
        # 找出最大步数
        max_dist = 0
        for i in range(n):
            for j in range(m):
                if maze[i][j] == '.' and dist[i][j] == -1:
                    return -1  # 存在不可达的可通行位置
                if maze[i][j] == '.':
                    max_dist = max(max_dist, dist[i][j])
        
        return max_dist

# 读取输入
n, m = map(int, input().split())
maze = [input() for _ in range(n)]
x0, y0 = map(int, input().split())
k = int(input())
moves = [tuple(map(int, input().split())) for _ in range(k)]

solution = Solution()
print(solution.solve(maze, x0, y0, moves))