【力扣】[劍指 Offer 12.] 矩陣中的路徑

一.題目

請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字串所有字元的路徑。路徑可以從矩陣中的任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經過了矩陣的某一格，那麼該路徑不能再次進入該格子。例如，在下面 下麪的3×4的矩陣中包含一條字串「bfce」的路徑（路徑中的字母用加粗標出）。

[[「a」,「b」,「c」,「e」], [「s」,「f」,「c」,「s」], [「a」,「d」,「e」,「e」]]

但矩陣中不包含字串「abfb」的路徑，因爲字串的第一個字元b佔據了矩陣中的第一行第二個格子之後，路徑不能再次進入這個格子。

鏈接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

二.程式碼展示

思路：這裏我們採用雙回圈遍歷對矩陣中的每一個字母進行操作，在_exist中，找下一個字母是不是符合的word裏面的，然後對運用遞回的方式，找其上下左右的字母是不是word裏面的下一個字母，以此類推，如果都找到了，就返回true，否則返回false；

bool _exist(char** board,int boardSize,int* boardColSize,char* word,int row,int col,int len)
{
    // 對邊界條件進行判斷，不是矩陣最後一個字母也返回false
    if(row < 0 || col < 0 || row >= boardSize ||col >= *boardColSize || board[row][col] != word[len] )
        return false;

    // 判斷是否完成路徑，完成路徑說明矩陣中還存在滿足條件的路徑
    // len 每次++ 直到相等的時候返回true，否則返回false
    if(strlen(word) - 1 == len)  
        return true;
    // 將當前的位置設定爲非字母，使得遞回時不會出現再次查詢的情況
    char tmp = board[row][col];
    board[row][col] = '*';
    // 從當前位置的上下左右遞回判斷四個方向是否存在滿足路徑的下一個節點
    // 不存在的話返回false，有的話返回true
    bool res = (_exist(board, boardSize, boardColSize, word, row, col + 1, len + 1) ||
               _exist(board, boardSize, boardColSize, word, row, col - 1, len + 1) ||
               _exist(board, boardSize, boardColSize, word, row + 1, col, len + 1) ||
               _exist(board, boardSize, boardColSize, word, row - 1, col, len + 1) );
    // 將該位置還原
    board[row][col] = tmp;
    return res;
}

bool exist(char** board, int boardSize, int* boardColSize, char* word){
    for(int i = 0; i < boardSize; i++)
    {
        for(int j = 0; j < *boardColSize; j++)
        {
            // 對矩陣中的所有字母開始遍歷，然後下一個字母如果存在的話，那麼一定返回true，否則返回false，知道返回true位置，回圈結束沒有返回true的話，直接返回false
            if(_exist(board, boardSize, boardColSize, word, i, j, 0))
                return true;
        }
    }
    return false;
}