二进制矩阵是指在计算机编程术语中，由0和1组成的行和列的网格。在编程面试和比赛中遇到的一个编码挑战是确定二进制矩阵中的退出点。在本文中，我们将解释使用C++解决这个问题的不同方法。

语法

在深入研究算法之前，我们可能会发现先熟悉一下在我们即将展示的代码示例中经常出现的语法会有益处。

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

算法

现在，让我们来概述一下在二进制矩阵中找到出口点的逐步算法 -

• 将当前单元格位置初始化为 (0, 0)。

• 从当前单元格开始遍历矩阵。

• 如果当前单元格为1，则按优先顺序移动到下一个单元格 - 右、下、左、上。

• 如果当前单元格为0，则退出循环，并将当前单元格位置作为退出点返回。

• 重复步骤3和4，直到找到退出点或所有单元格都被访问。

方法一

我们建议的第一种方法是通过实现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)

方法二

为了处理单元格移动，我们的第二种方法使用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)

Explanation

解释

函数 `findExitPoint` 在提供的代码中被设计出来。它的目的是接受一个二进制矩阵作为输入，并输出一对整数，这对整数对应于出口点的坐标。该函数遵循所述算法来遍历矩阵并找到出口点。

在使用两种实现技术遍历矩阵时，为了跟踪我们当前的单元格位置，我们利用变量`x`和`y`。然后，我们使用循环根据优先顺序移动矩阵：向右、向下、向左和向上。

采用while循环的方式，我们检查每个单元格的值，利用if-else语句。假设当前单元格为1，我们按照指定的方向移动到下一个单元格。如果当前单元格为0，我们跳出循环，并将当前单元格位置作为退出点返回。

方法2使用do-while循环和switch语句来处理单元格移动。为了有效地进行导航过程，我们采用基于条件的执行路径，专门针对与每个给定当前单元格值相对应的方向移动。实质上，当处理值为1的当前单元格时，会迅速进行调整，以适应我们x和y坐标值所需的任何必要修改。假设当前单元格为0，我们跳出循环。

在`main`函数中，我们初始化了一个二进制矩阵，并调用`findExitPoint`函数来获取出口点的坐标。最后，我们使用`cout`打印出口点的坐标。

结论

经常遇到的编程任务是在二进制矩阵中找到一个出口点，这个任务提出了各种解决路径。我们在这篇文章中深入探讨了两种不同的方法，这些方法是用C++代码实现的，用来解决这个障碍。成功应用这些算法可以高效地确定二进制矩阵的结束位置或者指向一个终点位置。请记住选择与您期望的编码风格偏好和最终目标相匹配的策略。