[65] The sword refers to the path in the offer->matrix

topic

Please design a function to determine whether there is a path containing all characters of a string in a matrix. The path can start from any cell in the matrix, and each step can move one cell left, right, up, and down in the matrix. If a path passes through a grid in the matrix, the path can no longer enter that grid. For example, the 3x4 matrix below contains a path to the string "bcced" (letters in the path are italicized). But the "abcb" path is not included in the matrix, because after the first character b of the string occupies the second cell in the first row of the matrix, the path cannot enter this cell again.

ideas

First, traversing this matrix, we can easily find the matrix element ch that is the same as the first character in the string str.

Then traverse the upper, lower, left and right characters of ch. If there is the same character as the next character in the string str, take that character as the next character (the starting point of the next traversal), if not, you need to go back to the previous one character, and then traverse again. To avoid path overlap, an auxiliary matrix is ​​needed to record path conditions.

In the following code, when the grid whose matrix coordinates are (row, col) is the same as the character with the subscript pathLength in the path string, the grid will start from 4 adjacent grids (row, col-1), (row-1, col) ), (row, col+1) and (row+1, col) to locate the character with subscript pathLength+1 in the path string.

If the four adjacent grids do not match the character with the subscript pathLength+1 in the string, it indicates that the character with the subscript pathLength in the current path string is not positioned correctly in the matrix, and we need to return to the previous string (pathLength-1), then reposition.

This process is repeated until all characters on the path string find the format position in the matrix (where str[pathLength] == '\0').

code

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(matrix == NULL || rows < 1 || cols < 1 || str == NULL){
            return false;
        }
        bool* visited = new bool[rows*cols];
        memset(visited, 0, rows*cols);
        int pathLength = 0;
        //Start traversing to find the path
        for(int row = 0; row < rows; row++){
            for(int col = 0; col < cols; col++){
                if(hasPathCore(matrix, rows, cols, row, col, str, pathLength, visited)){
                    delete[] visited;
                    return true;
                }
            }
        }
        delete[] visited;
        return false;
    }
private:
    bool hasPathCore(char* matrix, int rows, int cols, int row, int col, char* str, int& pathLength, bool* visited){
        if(str[pathLength] == '\0'){
            return true;
        }
        bool hasPath = false;
        if(row >= 0 && row < rows && col >= 0 && col < cols && matrix[row*cols+col] == str[pathLength] && !visited[row*cols+col]){
            //ptah length + 1, pointing to the next str
            ++pathLength;       --------------------------------------
            //mark the current position of the auxiliary matrix as true |
            visited[row*cols+col] = true;                             |    1.
            //Traverse the surrounding four nodes in turn |
            hasPath =                                                \  /
                                                                      \/
     ----------- hasPathCore(matrix, rows, cols, row-1, col, str, pathLength, visited)          3.
     |            || hasPathCore(matrix, rows, cols, row+1, col, str, pathLength, visited) <-----
     |           || hasPathCore(matrix, rows, cols, row, col-1, str, pathLength, visited)       |
     | 2.        || hasPathCore(matrix, rows, cols, row, col+1, str, pathLength, visited);      |
     |                                                                                          |
     |       //If the path is not found at the current location |
     -----> if(!hasPath){                                                                       |
                --pathLength;    ---------------------------------------------------------------
                visited[row*cols+col] = false;
            }
        }
        return hasPath;
    }
};

Tags: C++

Posted by jwb666 on Mon, 09 May 2022 14:34:39 +0300