LeetCode Ts-2556. Disconnect Path in a Binary Matrix by at Most One Flip

You are given a 0-indexed m x n binary matrix grid. You can move from a cell (row, col) to any of the cells (row + 1, col) or (row, col + 1) that has the value 1. The matrix is disconnected if there is no path from (0, 0) to (m – 1, n – 1).
You can flip the value of at most one (possibly none) cell. You cannot flip the cells (0, 0) and (m – 1, n – 1).
Return true if it is possible to make the matrix disconnect or false otherwise.
Note that flipping a cell changes its value from 0 to 1 or from 1 to 0.

你給予一個 index 為 0 的 m x n 二進制矩陣網格。
你可以從格子 (row, col) 移動到值為 1 的任何 (row + 1, cow) 或 (row, col + 1) 的格子。
如果沒有從 (0, 0) 到 (m - 1, n - 1) 的路徑，則矩陣將連結斷掉。
你最多可翻轉一個格子的值(也可能一個都不翻)。你不能翻轉 (0, 0) 和 (m - 1, n - 1) 的格子。
如果可以連結斷了，則回傳 true，否則回傳 false。
注意，翻轉格子會將其值從 0 變更為 1，或由 1 變更為 0。

Example 1:

Input: grid = [[1,1,1],[1,0,0],[1,1,1]]
Output: true
Explanation: We can change the cell shown in the diagram above. There is no path from (0, 0) to (2, 2) in the resulting grid.

Example 2:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: false
Explanation: It is not possible to change at most one cell such that there is not path from (0, 0) to (2, 2).

Solution:
這題的意思是，如果這個矩陣一開始可以從左上走到右下，
那可不可以翻轉最多 1 個格字的數值(也可以不翻)，讓這個左上到右下的連結斷掉。
我們先從左上走到右下，同時確認格子上方或左方能不能連接(是否為 1)，如果不能則設為0。
我們在從右下走到左上，同時確認格子下方或右方能不能連接(是否為 1)，如果不能則設為0。
最後我們沿著對角線確認 vis1, vis2 哪些格子兩邊都能連接，如果某條對角線可到達的格子為 <= 1， 則連接的路線可以斷開，回傳 true，否則回傳 false。 Code 1: BigO(m ^ 2 + m * n)

function isPossibleToCutPath(grid: number[][]): boolean {
    const m: number = grid.length;
    const n: number = grid[0].length;
    const vis1: number[][] = Array.from({length:m}, (_, i) => [...grid[i]]);
    const vis2: number[][] = Array.from({length: m}, (_, i) => [...grid[i]]);

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 && j === 0) continue;

            const fromTop: boolean = i !== 0 && vis1[i - 1][j] === 1;
            const fromLeft: boolean = j !== 0 && vis1[i][j - 1] === 1;
            if (!fromTop && ! fromLeft) {
                vis1[i][j] = 0;                
            }
        }
    }

    for (let i = m - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (i === m - 1 && j === n - 1) continue;

            const fromBottom: boolean = i !== m - 1 && vis2[i + 1][j] === 1;
            const fromRight: boolean = j !== n - 1 && vis2[i][j + 1] === 1;
            if (!fromBottom && !fromRight) {
                vis2[i][j] = 0;            
            }
        }
    }

    for (let x = 1; x < m + n - 2; x++) {
        let count: number = 0;
        for (let y = 0; y < m; y++) {
            const s = x - y;
            if (s < 0 || s >= n) continue;
            if (vis1[y][s] === 1 && vis2[y][s] === 1) count++;                    
        }
        if (count <= 1) return true;
    }

    return false;
};

FlowChart:
Example 1

Input: grid = [[1,1,1],[1,0,0],[1,1,1]]

vis1 [ 
    -> [ 1, 1, 1 ],
    -> [ 1, 0, 0 ],
    -> [ 1, 1, 1 ] 
     ]
vis2 [ 
       [ 1, 0, 0 ], <-
       [ 1, 0, 0 ], <- 
       [ 1, 1, 1 ]  <- 
     ]
mapping [                 [               [              [
          [ 1, 0, 0 ],      [ 1, ●, 0]      [ 1, 0, ●]     [ 1, 0, 0]
          [ 1, 0, 0 ], ->   [ ●, 0, 0] ->   [ 1, ●, 0] ->  [ 1, 0, ●]
          [ 1, 1, 1 ]       [ 1, 1, 1]      [ ●, 1, 1]     [ 1, ●, 1]
        ]                 [               [              [
                            count = 0
                            count = 1
                            return true;

Example 2

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]

vis1 [ 
   ->  [ 1, 1, 1 ], 
   ->  [ 1, 0, 1 ], 
   ->  [ 1, 1, 1 ] 
     ]
vis2 [ 
       [ 1, 1, 1 ], <-
       [ 1, 0, 1 ], <-
       [ 1, 1, 1 ]  <-
     ]
mapping [                 [               [              [
          [ 1, 1, 1 ],      [ 1, ●, 0]      [ 1, 0, ●]     [ 1, 0, 0]
          [ 1, 0, 1 ], ->   [ ●, 0, 0] ->   [ 1, ●, 0] ->  [ 1, 0, ●]
          [ 1, 1, 1 ]       [ 1, 1, 1]      [ ●, 1, 1]     [ 1, ●, 1]
        ]                 [               [              [
                            count = 1       count = 1      count = 1
                            count = 2       count = 1      count = 2
                                            count = 2
                            return false;