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;
}