檢查一個值為 1 的單元格是否存在路徑到達矩陣的右下角，且在任何值為 2 的單元格到達之前。

---

涉及網格和矩陣的問題大多使用 BFS 或 DFS 遍歷演算法解決。先來看一下第一個演算法：

廣度優先遍歷 - BFS 或廣度優先遍歷是一種用於搜尋樹或圖資料結構的演算法。它從根節點開始，在移動到下一層之前探索當前層的所有節點。

演算法

procedure BFS(G, root) is
   let Q be a queue
   label root as explored
   Q.enqueue(root)
   while Q is not empty do
      v := Q.dequeue()
      if v is the goal then
         return v
      for all edges from v to w in G.adjacentEdges(v) do
         if w is not labelled as explored then
            label w as explored
            w.parent := v
            Q.enqueue(w)

問題陳述

給定一個矩陣 arr[][]，其中只有 0、1 和 2。任務是找出 1 是否可以在 2 之前到達矩陣的右下角。

約束條件

• 矩陣中可以存在多個 2，但只能存在一個 1。

• 1 和 2 都可以向四個方向移動，即上、下、左和右，但只能移動到值為 0 的單元格。

示例 1

輸入

arr[][] = 
{{0, 2, 0},
{0, 2, 0},
{0, 1, 0}}

輸出

True

解釋

1 可以用 1 步 (R) 到達右下角，而 2 需要 2 步 (RD)。因此，1 在 2 之前到達右下角。

示例 2

輸入

arr[][] = 
{{0, 2, 0},
{0, 1, 0},
{0, 2, 0}}

輸出

False

解釋

2 可以用 1 步 (R) 到達右下角，而 1 需要 2 步 (RD)。因此，2 在 1 之前到達右下角。

解決方案方法：廣度優先搜尋遍歷

使用雙端佇列資料結構，我們對矩陣應用 BFS 以查詢 1 是否在 2 之前到達右下角。在雙端佇列中，將 1 推入前端，將 2 推入後端，以便如果 1 和 2 同時到達，則優先考慮 1。然後從雙端佇列中彈出元素，並檢視是否可以到達右下角。

虛擬碼

function oneTwo(arr: 2D array of integers):
   n := number of rows of arr
   m := number of columns of arr
   q := empty deque of vectors of integers
    
   for i from 0 to n-1:
      for j from 0 to m-1:
         if arr[i][j] is 1:
            push {i, j, 1} to front of q
         else if arr[i][j] is 2:
            push {i, j, 2} to back of q
         set arr[i][j] to 0
      
   del_x := [0, 1, 0, -1]
   del_y := [-1, 0, 1, 0]
   while q is not empty:
      front := q.front()
      pop front element from q
      i := front[0]
      j := front[1]
      num := front[2]        
      if arr[i][j] is not 0:
         continue        
      set arr[i][j] to 1        
      if num is 1 and (i is n-1 and j is m-1):
         return True
      for d from 0 to 3:
         neighbour_i := i + del_x[d]
         neighbour_j := j + del_y[d]
         if neighbour_i is between 0 and n-1 and neighbour_j is between 0 and m-1:
            push {neighbour_i, neighbour_j, num} to back of q
   return False

示例：C++ 實現

以下程式使用 BFS 遍歷演算法。

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

// Function to find if 1 reaches bottom right corner before 2
bool oneTwo(vector<vector<int>> &arr){
   int n = arr.size();
   int m = arr[0].size();
   deque<vector<int>> q;
   // Adding 1 to front of queue and 2 to back of queue
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
         if (arr[i][j] == 1) {
            q.push_front({i, j, 1});
         } else if (arr[i][j] == 2) {
            q.push_back({i, j, 2});
         }
         arr[i][j] = 0;
      }
   }

   int del_x[] = {0, 1, 0, -1};
   int del_y[] = {-1, 0, 1, 0};

   while (!q.empty()) {
      auto front = q.front();
      q.pop_front();
      int i = front[0], j = front[1], num = front[2];
      if (arr[i][j]) {
         continue;
      }
      arr[i][j] = 1;
      // Checking if 1 reached the bottom right corner first
      if (num == 1 and (i == n - 1 && j == m - 1)) {
         return true;
      }
      for (int d = 0; d < 4; d++) {
         int neighbour_i = i + del_x[d];
         int neighbour_j = j + del_y[d];
         if (neighbour_i >= 0 and neighbour_i < n and neighbour_j >= 0 and neighbour_j < m) {
            q.push_back({neighbour_i, neighbour_j, num});
         }
      }
   }
   return false;
}
int main(){
   vector<vector<int>> arr{{0, 2, 0},
      {0, 2, 0},
      {0, 1, 0}};
   if (oneTwo(arr)){
      cout << "True";
   } else {
      cout << "False";
   }
   return 0;
}

輸出

True

時間複雜度 - O(N*M)，其中 N*M 是矩陣的維度。這是因為我們遍歷了矩陣中的所有元素。

空間複雜度 - O(N*M)，其中 N*M 是矩陣的維度。這是因為雙端佇列儲存了矩陣的所有可能方向。

結論

總之，提供的解決方案使用了多源 BFS 並使用了雙端佇列資料結構來優先考慮 1 而不是 2。解決方案的時間和空間複雜度為 O(N*M)，其中 N*M 是矩陣的維度。