题解 | 蘑菇阵

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

class Solution {
public:
    double safePath(int n, int m, vector<pair<int,int>>& mushrooms) {
        vector<vector<bool>> hasMushroom(n + 1, vector<bool>(m + 1, false));
        for (const auto& pos : mushrooms) {
            hasMushroom[pos.first][pos.second] = true;
        }
        
        if (hasMushroom[n][m]) return 0.0;
        
        vector<vector<double>> dp(n + 1, vector<double>(m + 1, 0.0));
        dp[n][m] = 1.0;
        
        for (int i = n; i >= 1; i--) {
            for (int j = m; j >= 1; j--) {
                if ((i == n && j == m) || hasMushroom[i][j]) continue;
                
                int moves = 0;
                double prob = 0.0;
                
                if (j < m) {
                    moves++;
                    prob += dp[i][j + 1];
                }
                if (i < n) {
                    moves++;
                    prob += dp[i + 1][j];
                }
                
                if (moves > 0) {
                    dp[i][j] = prob / moves;
                }
            }
        }
        
        return dp[1][1];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(2);
    
    int n, m, k;
    while (cin >> n >> m >> k) {
        vector<pair<int,int>> mushrooms;
        for (int i = 0; i < k; i++) {
            int x, y;
            cin >> x >> y;
            mushrooms.emplace_back(x, y);
        }
        
        Solution solution;
        cout << solution.safePath(n, m, mushrooms) << endl;
    }
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public double safePath(int n, int m, int[][] mushrooms) {
            boolean[][] hasMushroom = new boolean[n + 1][m + 1];
            for (int[] pos : mushrooms) {
                hasMushroom[pos[0]][pos[1]] = true;
            }
            
            if (hasMushroom[n][m]) return 0.0;
            
            double[][] dp = new double[n + 1][m + 1];
            dp[n][m] = 1.0;
            
            for (int i = n; i >= 1; i--) {
                for (int j = m; j >= 1; j--) {
                    if ((i == n && j == m) || hasMushroom[i][j]) continue;
                    
                    int moves = 0;
                    double prob = 0.0;
                    
                    if (j < m) {
                        moves++;
                        prob += dp[i][j + 1];
                    }
                    if (i < n) {
                        moves++;
                        prob += dp[i + 1][j];
                    }
                    
                    if (moves > 0) {
                        dp[i][j] = prob / moves;
                    }
                }
            }
            
            return dp[1][1];
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int k = sc.nextInt();
            
            int[][] mushrooms = new int[k][2];
            for (int i = 0; i < k; i++) {
                mushrooms[i][0] = sc.nextInt();
                mushrooms[i][1] = sc.nextInt();
            }
            
            Solution solution = new Solution();
            System.out.printf("%.2f%n", solution.safePath(n, m, mushrooms));
        }
        sc.close();
    }
}

def safe_path(n, m, mushrooms):
    has_mushroom = [[False] * (m + 1) for _ in range(n + 1)]
    for x, y in mushrooms:
        has_mushroom[x][y] = True
    
    if has_mushroom[n][m]:
        return 0.0
    
    dp = [[0.0] * (m + 1) for _ in range(n + 1)]
    dp[n][m] = 1.0
    
    for i in range(n, 0, -1):
        for j in range(m, 0, -1):
            if (i == n and j == m) or has_mushroom[i][j]:
                continue
            
            moves = 0
            prob = 0.0
            
            if j < m:
                moves += 1
                prob += dp[i][j + 1]
            if i < n:
                moves += 1
                prob += dp[i + 1][j]
            
            if moves > 0:
                dp[i][j] = prob / moves
    
    return dp[1][1]

def main():
    while True:
        try:
            n, m, k = map(int, input().split())
            mushrooms = []
            for _ in range(k):
                x, y = map(int, input().split())
                mushrooms.append((x, y))
            
            result = safe_path(n, m, mushrooms)
            print(f"{result:.2f}")
        except EOFError:
            break

if __name__ == "__main__":
    main()