fork download
copy 
  1. /*
  2. QUESTION 3: Path Break Probability in a Directed Grid
  3.  
  4. Problem Statement:
  5. You are given a grid of open and blocked cells.
  6.  
  7. '.' means open.
  8. '#' means blocked.
  9.  
  10. You start from the top-left cell and want to reach the bottom-right cell.
  11. You may only move right or down.
  12.  
  13. Exactly one open cell is chosen uniformly at random and blocked.
  14.  
  15. Find the probability that after blocking this cell, no valid path remains.
  16. Return the probability modulo 1e9 + 7.
  17.  
  18. Hard Constraints:
  19. 1 <= N, M
  20. N * M <= 200000
  21.  
  22. Example:
  23. grid =
  24. [
  25.   "..",
  26.   ".."
  27. ]
  28.  
  29. Expected Output:
  30. 500000004
  31.  
  32. Explanation:
  33. There are 4 open cells.
  34. If start or destination is blocked, no path remains.
  35. If either of the other two cells is blocked, one path still remains.
  36.  
  37. Probability = 2 / 4 = 1 / 2
  38. Modulo 1e9 + 7, this is 500000004.
  39.  
  40. Brute Force:
  41. For every open cell:
  42. - Temporarily block it.
  43. - Run reachability DP.
  44. - Count how many choices break all paths.
  45.  
  46. Time Complexity:
  47. O(F * N * M)
  48.  
  49. Optimized Approach:
  50. Compute:
  51. fromStart[i][j] = whether cell can be reached from start.
  52. toEnd[i][j] = whether destination can be reached from this cell.
  53.  
  54. A useful cell lies on some valid path if both are true.
  55.  
  56. Every right/down path crosses exactly one cell on every diagonal i + j.
  57. If a diagonal contains only one useful cell, every path must pass through it.
  58.  
  59. Time Complexity:
  60. O(N * M)
  61.  
  62. Space Complexity:
  63. O(N * M)
  64. */
  65.  
  66. #include <bits/stdc++.h>
  67. using namespace std;
  68.  
  69. class Solution {
  70. public:
  71.     static const long long MOD = 1000000007;
  72.  
  73.     long long modpow(long long a, long long e) {
  74.         long long res = 1;
  75.  
  76.         while (e > 0) {
  77.             if (e & 1) res = res * a % MOD;
  78.             a = a * a % MOD;
  79.             e >>= 1;
  80.         }
  81.  
  82.         return res;
  83.     }
  84.  
  85.     int pathFailureProbability(vector<string>& grid) {
  86.         int n = grid.size();
  87.         int m = grid[0].size();
  88.  
  89.         int freeCells = 0;
  90.  
  91.         for (int i = 0; i < n; i++) {
  92.             for (int j = 0; j < m; j++) {
  93.                 if (grid[i][j] == '.') freeCells++;
  94.             }
  95.         }
  96.  
  97.         vector<vector<int>> fromStart(n, vector<int>(m, 0));
  98.         vector<vector<int>> toEnd(n, vector<int>(m, 0));
  99.  
  100.         if (grid[0][0] == '.') {
  101.             fromStart[0][0] = 1;
  102.  
  103.             for (int i = 0; i < n; i++) {
  104.                 for (int j = 0; j < m; j++) {
  105.                     if (grid[i][j] == '#') continue;
  106.  
  107.                     if (i > 0 && fromStart[i - 1][j]) fromStart[i][j] = 1;
  108.                     if (j > 0 && fromStart[i][j - 1]) fromStart[i][j] = 1;
  109.                 }
  110.             }
  111.         }
  112.  
  113.         if (grid[n - 1][m - 1] == '.') {
  114.             toEnd[n - 1][m - 1] = 1;
  115.  
  116.             for (int i = n - 1; i >= 0; i--) {
  117.                 for (int j = m - 1; j >= 0; j--) {
  118.                     if (grid[i][j] == '#') continue;
  119.  
  120.                     if (i + 1 < n && toEnd[i + 1][j]) toEnd[i][j] = 1;
  121.                     if (j + 1 < m && toEnd[i][j + 1]) toEnd[i][j] = 1;
  122.                 }
  123.             }
  124.         }
  125.  
  126.         if (!fromStart[n - 1][m - 1]) return 1;
  127.  
  128.         vector<int> diagonalUsefulCount(n + m - 1, 0);
  129.  
  130.         for (int i = 0; i < n; i++) {
  131.             for (int j = 0; j < m; j++) {
  132.                 if (grid[i][j] == '.' && fromStart[i][j] && toEnd[i][j]) {
  133.                     diagonalUsefulCount[i + j]++;
  134.                 }
  135.             }
  136.         }
  137.  
  138.         long long critical = 0;
  139.  
  140.         for (int i = 0; i < n; i++) {
  141.             for (int j = 0; j < m; j++) {
  142.                 if (grid[i][j] == '.' && fromStart[i][j] && toEnd[i][j]) {
  143.                     if (diagonalUsefulCount[i + j] == 1) {
  144.                         critical++;
  145.                     }
  146.                 }
  147.             }
  148.         }
  149.  
  150.         return critical * modpow(freeCells, MOD - 2) % MOD;
  151.     }
  152. };
  153.  
  154. int main() {
  155.     Solution sol;
  156.  
  157.     vector<string> grid = {
  158.         "..",
  159.         ".."
  160.     };
  161.  
  162.     cout << sol.pathFailureProbability(grid) << endl;
  163.  
  164.     return 0;
  165. }
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
500000004
https://ideone.com/hzMjjF
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!