使用 C++ 在二進位制矩陣中查找出口點

---

在計算機程式設計領域，二進位制矩陣指的是一個網格，其行和列僅由 0 或 1 組成。在程式設計面試和競賽中，識別二進位制矩陣中的出口點是一個常見的編碼挑戰。在這篇文章中，我們將解釋使用 C++ 解決此問題的不同方法。

語法

在深入研究演算法之前，首先熟悉我們即將在程式碼示例中使用的語法可能會有所幫助。

`pair<int, int> findExitPoint(const vector<vector<int>>& matrix)`.

演算法

現在，讓我們概述在二進位制矩陣中查找出口點的分步演算法：

• 將當前單元格位置初始化為 (0, 0)。

• 從當前單元格開始遍歷矩陣。

• 如果當前單元格為 1，則按照優先順序順序移動到下一個單元格：右、下、左、上。

• 如果當前單元格為 0，則退出迴圈並將當前單元格位置作為出口點返回。

• 重複步驟 3 和 4，直到找到出口點或訪問完所有單元格。

方法 1

在方法 1 中，我們建議用於執行演算法的方法圍繞實現 while 迴圈和條件語句。作為參考，以下是此實現的示例：

示例

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

pair<int, int> findExitPoint(const vector<vector<int>>& matrix) {
   int rows = matrix.size();
   int cols = matrix[0].size();
   int x = 0, y = 0;  // Starting cell position

   while (x >= 0 && x < rows && y >= 0 && y < cols) {
      if (matrix[x][y] == 1) {
         // Move right
         if (y + 1 < cols && matrix[x][y + 1] == 1)
            y++;
         // Move down
         else if (x + 1 < rows && matrix[x + 1][y] == 1)
            x++;
         // Move left
         else if (y - 1 >= 0 && matrix[x][y - 1] == 1)
            y--;
         // Move up
         else if (x - 1 >= 0 && matrix[x - 1][y] == 1)
            x--;
      } else {
         break;  // Exit loop when encountering a 0
      }
   }

   return make_pair(x, y);
}

int main() {
   // Matrix initialization
   vector<vector<int>> matrix = {
      {1, 0, 0, 1},
      {1, 1, 0, 1},
      {0, 1, 1, 1},
      {0, 0, 0, 1}
   };

   // Finding the exit point
   pair<int, int> exitPoint = findExitPoint(matrix);

   // Printing the exit point coordinates
   cout << "Exit Point: (" << exitPoint.first << ", " << exitPoint.second << ")" << endl;

   return 0;
}

輸出

Exit Point: (3, 3)

方法 2

為了處理單元格移動，我們的第二種方法使用 do while 迴圈以及 switch 語句。作為參考，以下是此實現的示例：

示例

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

pair<int, int> findExitPoint(const vector<vector<int>>& matrix) {
   int rows = matrix.size();
   int cols = matrix[0].size();
   int x = 0, y = 0;  // Starting cell position

   do {
      switch (matrix[x][y]) {
         case 1:  // Move based on the priority order
            if (y + 1 < cols && matrix[x][y + 1] == 1) {
               y++;  // Move right
            } else if (x + 1 < rows && matrix[x + 1][y] == 1) {
               x++;  // Move down
            } else if (y - 1 >= 0 && matrix[x][y - 1] == 1) {
               y--;  // Move left
            } else if (x - 1 >= 0 && matrix[x - 1][y] == 1) {
               x--;  // Move up
            }
            break;
   
            default:  // Exit loop when encountering a 0
         break;
      }
   } while (x >= 0 && x < rows && y >= 0 && y < cols);

   return make_pair(x, y);
}

int main() {
   // Matrix initialization
   vector<vector<int>> matrix = {
      {1, 0, 0, 1},
      {1, 1, 0, 1},
      {0, 1, 1, 1},
      {0, 0, 0, 1}
   };

   // Finding the exit point
   pair<int, int> exitPoint = findExitPoint(matrix);
   
   // Printing the exit point coordinates
   cout << "Exit Point: (" << exitPoint.first << ", " << exitPoint.second << ")" << endl;

   return 0;
}

輸出

Exit Point: (3, 3)

解釋

在提供的程式碼中建立了函式 `findExitPoint`。它的目的是接收一個二進位制矩陣作為輸入，並輸出一對整數，分別對應於出口點的座標。該函式遵循概述的演算法遍歷矩陣並找到出口點。

為了在使用兩種實現技術之一遍歷矩陣時跟蹤我們當前的單元格位置，我們利用變數 `x` 和 `y`。然後，我們使用迴圈根據優先順序順序遍歷矩陣：右、下、左和上。

方法 1 使用 while 迴圈，我們使用 if-else 語句檢查每個單元格的值。假設當前單元格為 1，我們則向指定方向移動到下一個單元格。如果當前單元格為 0，我們則退出迴圈並將當前單元格位置作為出口點返回。

方法 2 使用 do-while 迴圈和 switch 語句來處理單元格移動。為了有效地推進我們的導航過程，我們使用基於條件的執行路徑，這些路徑專門針對與每個給定當前單元格值相對應的方向移動。從本質上講，當處理值為 1 的當前單元格時，會迅速進行調整以適應我們 x 和 y 座標值所需的任何更改。假設當前單元格為 0，我們則退出迴圈。

在 `main` 函式中，我們初始化一個二進位制矩陣並呼叫 `findExitPoint` 函式以獲取出口點座標。最後，我們使用 `cout` 打印出口點座標。

結論

在二進位制矩陣中查找出口點是一個常見的程式設計任務，它提供了各種解決路徑。我們在這篇文章中深入探討了兩種在 C++ 程式碼中實現的不同方法來解決此問題。成功應用這些演算法可以有效地輸出識別二進位制矩陣在哪裡結束或通往端點位置。請記住選擇適合您所需編碼風格偏好和最終目標的策略。