<劍指Offer>面試題12:矩陣中的路徑

題目描述

  • 請設(shè)計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。
  • 路徑可以從矩陣中的任意一個格子開始，每一步可以在矩陣中向左，向右，向上，向下移動一個格子。
  • 如果一條路徑經(jīng)過了矩陣中的某一個格子，則之后不能再次進(jìn)入這個格子。

  • 例如，在下面的 3 X 4 矩陣中包含一條字符串 "bfce" 的路徑，但是矩陣中不包含"abfb"路徑，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后，路徑不能再次進(jìn)入該格子。

題目解讀

  • 劍指Offer 89

解題思路

  • 回溯法
  • 思路一：和課本思路一致，將二維矩陣放入一維數(shù)組中，以后推薦這種思想
    因為用二維數(shù)組處理時，涉及輔助函數(shù)傳遞參數(shù)時不方便
  • 思路二：和思路一思想一致只是里面實現(xiàn)代碼有些許差別，特此提出，以供思考
  • 思路三：和課本思路一致，將二維矩陣放入二維數(shù)組中

代碼

  • 思路一：和課本思路一致，將二維矩陣放入一維數(shù)組中
    兩套代碼實現(xiàn)，第一套代碼更加優(yōu)越，仔細(xì)看代碼哦
class Solution {
public:
    bool core(char* matrix, int& rows, int& cols, char* str, int& len,
             int *visit, int i, int j, int index){
        bool flag = false;
        if(str[index] == matrix[i * cols + j]){
            visit[i * cols + j] = 1;
            ++index;
        }
        else{
            return false;
        }
        if(index == len){
            flag = true;
        }
        
        // 向上
        if(flag == false && i-1>=0 && visit[(i-1)*cols + j] == 0){
            flag = core(matrix, rows, cols, str, len, visit, i-1, j, index);
        }
        // 向下
        if(flag == false && i+1<rows && visit[(i+1)*cols + j] == 0){
            flag = core(matrix, rows, cols, str, len, visit, i+1, j, index);
        }
        // 向左
        if(flag == false && j-1>=0 && visit[i*cols + j-1] == 0){
            flag = core(matrix, rows, cols, str, len, visit, i, j-1, index);
        }
        // 向右
        if(flag == false && j+1<cols && visit[i*cols + j+1] == 0){
            flag = core(matrix, rows, cols, str, len, visit, i, j+1, index);
        }
        return flag;
    }
    void init_visit(int *visit, int size){
        for(int i=0; i < size; ++i){
                visit[i] = 0;
        }
    }
    
    bool hasPath(char* matrix, int rows, int cols, char* str){
        int len = strlen(str);
        int visit[rows * cols];
        int index = 0;
        init_visit(visit, rows * cols);
        
        for(int i=0; i < rows; ++i){
            for(int j=0; j < cols; ++j){
                cout << matrix[i * cols + j] << endl;
                if(core(matrix, rows, cols, str, len, visit, i, j, index)){
                    return true;
                }
                init_visit(visit, rows * cols);
            }
        }
        return false;
    }
};

#include<iostream>
#include<cstring>
using namespace std;

class Solution {
public:
    bool hasPathCore(int row, int col, int rows, int cols, char *matrix, int *visited, char* str, int length){
        bool shang, xia, zuo, you;

        if(matrix[row * cols + col] == str[length]){
            visited[row * cols + col] = 1;
            length += 1;

            if(strlen(str) == length){
                return true;
            }

            // 上
            if(row > 0 && visited[(row-1) * cols + col]==0){
                shang = hasPathCore(row-1, col, rows, cols, matrix, visited, str, length);
            }else{
                shang = false;
            }

            // 下
            if(row < rows-1 && visited[(row+1) * cols + col]==0){
                xia = hasPathCore(row+1, col, rows, cols, matrix, visited, str, length);
            }else{
                xia = false;
            }

            // 左
            if(col > 0 && visited[row * cols + col-1]==0){
                zuo = hasPathCore(row, col-1, rows, cols, matrix, visited, str, length);
            }else{
                zuo = false;
            }

            // 右
            if(col < cols-1 && visited[row * cols + col+1]==0){
                you = hasPathCore(row, col+1, rows, cols, matrix, visited, str, length);
            }else{
                you = false;
            }

            if(shang || xia || zuo || you){
                return true;
            }
        }
        
        return false;
    }

    void init_visited(int *visited, int size){
        for(int i=0; i < size; i++){
                visited[i] = 0;
        }
    }

    bool hasPath(char *matrix, int rows, int cols, char* str){

        if(matrix == NULL || rows < 1 || cols < 1 || str == NULL){
            return false;
        }

        int length = 0;
        int visited[rows * cols];

        init_visited(visited, rows*cols);

        for(int i=0; i < rows; i++){
            for(int j=0; j < cols; j++){
                if(hasPathCore(i, j, rows, cols, matrix, visited, str, length)){
                    // 輸出可以看到該字符串在矩陣中的路徑
                    // for(int k = 0; k < rows*cols; k++){
                    //  cout<<visited[k]<<" ";
                    // }
                    // cout<<endl;
                    return true;
                }
                // 這句話最好加上，但是不加上也能得到正確結(jié)果
                // 功能為：消除在visited中上一個格子走過的路徑(全部為0)
                 init_visited(visited, rows*cols);
            }
        }
        return false;
    }
};


int main(){
    Solution ss;
    char str[20] = "bfce";
    // char str[20] = "AAAAAAAAAAAA";
    int rows = 3;
    int cols = 4;
    char matrix[rows * cols] = {'a', 'b', 't', 'g', 'c', 'f', 'c', 's', 'j', 'd', 'e', 'h'};
    // char matrix[rows * cols] = {'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A', 'A'};
    bool bb;

    bb = ss.hasPath(matrix, rows, cols, str);
    cout<<bb<<endl;
}
  • 思路二代碼 ，和思路一思想一致只是里面實現(xiàn)代碼有些許差別，特此提出，以供思考
class Solution {
public:
    bool hasPathCore(int row, int col, int rows, int cols, char *matrix, int *visited, char* str, int length){
        bool shang=false, xia=false, zuo=false, you=false;

        if(matrix[row * cols + col] == str[length]){
            visited[row * cols + col] = 1;
            length += 1;

            if(strlen(str) == length){
                return true;
            }

            // 上
            if(row > 0 && visited[(row-1) * cols + col]==0){
                shang = hasPathCore(row-1, col, rows, cols, matrix, visited, str, length);
            }

            // 下
            if(row < rows-1 && visited[(row+1) * cols + col]==0){
                xia = hasPathCore(row+1, col, rows, cols, matrix, visited, str, length);
            }

            // 左
            if(col > 0 && visited[row * cols + col-1]==0){
                zuo = hasPathCore(row, col-1, rows, cols, matrix, visited, str, length);
            }

            // 右
            if(col < cols-1 && visited[row * cols + col+1]==0){
                you = hasPathCore(row, col+1, rows, cols, matrix, visited, str, length);
            }

            if(shang || xia || zuo || you){
                return true;
            }
        }
        return false;
    }

    bool hasPath(char *matrix, int rows, int cols, char* str){
        if(matrix == NULL || rows < 1 || cols < 1 || str == NULL){
            return false;
        }

        int length = 0;
        int visited[rows * cols];
        // 將 visited 初始化為全0
        memset(visited, 0, (rows*cols)*sizeof(int));

        for(int i=0; i < rows; i++){
            for(int j=0; j < cols; j++){
                if(hasPathCore(i, j, rows, cols, matrix, visited, str, length)){
                    // 輸出可以看到該字符串在矩陣中的路徑
                    // for(int k = 0; k < rows*cols; k++){
                    //  cout<<visited[k]<<" ";
                    // }
                    // cout<<endl;
                    return true;
                }
                // 這句話最好加上，但是不加上也能得到正確結(jié)果
                // 功能為：消除在visited中上一個格子走過的路徑(全部為0)
                memset(visited, 0, (rows*cols)*sizeof(int));
            }
        }
        return false;
    }
};

思路三代碼

#include<iostream>
#include<cstring>
using namespace std;

#define rows 3
#define cols 4

class Solution {
public:
    bool hasPathCore(int row, int col, char matrix[][cols], int visited[][cols], char* str, int length){
        bool shang, xia, zuo, you;

        if(matrix[row][col] == str[length]){
            visited[row][col] = 1;
            length += 1;

            if(strlen(str) == length){
                return true;
            }

            // 上
            if(row > 0 && visited[row-1][col]==0){
                shang = hasPathCore(row-1, col, matrix, visited, str, length);
            }else{
                shang = false;
            }

            // 下
            if(row < rows-1 && visited[row+1][col]==0){
                xia = hasPathCore(row+1, col, matrix, visited, str, length);
            }else{
                xia = false;
            }

            // 左
            if(col > 0 && visited[row][col-1]==0){
                zuo = hasPathCore(row, col-1, matrix, visited, str, length);
            }else{
                zuo = false;
            }

            // 右
            if(col < cols-1 && visited[row][col+1]==0){
                you = hasPathCore(row, col+1, matrix, visited, str, length);
            }else{
                you = false;
            }

            if(shang || xia || zuo || you){
                return true;
            }
        }
        
        return false;
    }

    void init_visited(int visited[][cols]){
        for(int i=0; i < rows; i++){
            for(int j=0; j < cols; j++){
                visited[i][j] = 0;
            }
        }
    }

    bool hasPath(char matrix[][cols], char* str){
        int length = 0;
        int visited[rows][cols];

        init_visited(visited);

        for(int i=0; i < rows; i++){
            for(int j=0; j < cols; j++){
                if(hasPathCore(i, j, matrix, visited, str, length)){
                    return true;
                }
                init_visited(visited);
            }
        }
        return false;
    }
};


int main()
{
    Solution ss;
    char str[20] = "bfce";
    char matrix[rows][cols] = {{'a', 'b', 't', 'g'}, {'c', 'f', 'c', 's'}, {'j', 'd', 'e', 'h'}};
    // char str[20] = "AAAAAAAAAAAA";
    // char matrix[rows][cols] = {{'A', 'A', 'A', 'A'}, {'A', 'A', 'A', 'A'}, {'A', 'A', 'A', 'A'}};
    
    cout<<ss.hasPath(matrix, str)<<endl;
}

總結(jié)展望

  • 回溯法思想解決的經(jīng)典題型，值得回味，推薦！
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容