使用 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++ 代码中实现的不同方法来解决此问题。成功应用这些算法可以有效地输出识别二进制矩阵在哪里结束或通往端点位置。请记住选择适合您所需编码风格偏好和最终目标的策略。