Translate exit points in binary matrix using C++

A binary matrix refers, in computer programming terms, to a grid of rows and columns composed of 0s and 1s. One coding challenge encountered in programming interviews and competitions is determining exit points in binary matrices. In this article, we will explain different ways to solve this problem using C.

grammar

Before delving into the algorithm, we may find it beneficial to familiarize ourselves with the syntax that appears frequently in the code examples we are about to show.

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

algorithm

Now, let us outline the step-by-step algorithm for finding the exit point in a binary matrix -

• Initialize the current cell position to (0, 0).

• Traverse the matrix starting from the current cell.

• If the current cell is 1, move to the next cell in order of priority - right, bottom, left, top.

• If the current cell is 0, exit the loop and return the current cell position as the exit point.

• Repeat steps 3 and 4 until the exit point is found or all cells have been visited.

method one

The first approach we recommend is by implementing a while loop and conditional statements to execute the algorithm. Here is an example showing what such an implementation would look like -

Example

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

Output

Exit Point: (3, 3)

Method Two

To handle cell movement, our second method uses a do while loop combined with a switch statement. For reference, here is an example showing what such an implementation would look like −

Example

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

Output

Exit Point: (3, 3)

The Chinese translation of

Explanation

is:

Explanation

The function `findExitPoint` is designed in the provided code. Its purpose is to accept a binary matrix as input and output a pair of integers corresponding to the coordinates of the exit point. This function follows the algorithm described to traverse the matrix and find the exit point.

To keep track of our current cell position when traversing the matrix using both implementation techniques, we utilize the variables `x` and `y`. We then use a loop to move the matrix according to order of precedence: right, down, left, and up.

Using a while loop, we check the value of each cell and use if-else statements. Assuming the current cell is 1, we move to the next cell in the specified direction. If the current cell is 0, we break out of the loop and return the current cell position as the exit point.

Method 2 uses a do-while loop and switch statement to handle cell movement. To make the navigation process efficient, we employ a condition-based execution path that specifically targets moves in the direction corresponding to each given current cell value. Essentially, when the current cell with a value of 1 is processed, it is quickly adjusted to accommodate any necessary modifications required to our x and y coordinate values. Assuming that the current cell is 0, we break out of the loop.

In the `main` function, we initialize a binary matrix and call the `findExitPoint` function to obtain the coordinates of the exit point. Finally, we use `cout` to print the coordinates of the exit point.

in conclusion

A frequently encountered programming task is to find an exit point in a binary matrix, and this task proposes various solution paths. In this article we take a deep dive into two different methods, implemented in C code, to overcome this obstacle. Successful application of these algorithms can efficiently determine the end position of a binary matrix or point to an end position. Remember to choose a strategy that matches your desired coding style preferences and end goals.

The above is the detailed content of Translate exit points in binary matrix using C++. For more information, please follow other related articles on the PHP Chinese website!