(每日算法)LeetCode --- Word Search(矩陣中查找單詞)

(每日算法)LeetCode --- Word Search(矩陣中查找單詞)

在矩陣中查找給定的單詞是否出現，可以向上、向下、向左和向右查找。不能在一個字母上重復查找。

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

//如何構造輔助函數的參數？
//逐個字母匹配的時候，如何傳遞下一個要匹配的字母？---通過索引參數的形式
//走過的路要標記，不管可行不可行，都要重新標記？
//邊界條件的考慮？
class Solution {
public:
    bool exist(vector> &board, string word) {
        const int m = board.size();
        const int n = board[0].size();
        vector> visited(m, vector(n, false));//將訪問標記數組置空
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(dfs(board, word, 0, i, j, visited))//單詞可在任意位置開始匹配
                    return true;                      //只要有一個位置完全匹配即匹配
        return false;
    }
    static bool dfs(vector> &board, string word, int index,
                    int x, int y, vector>& visited)//輔助函數，自定義參數
    {
        if(index == word.size())    //單詞大小和索引相等即匹配
                                    //當單詞為空的時候是滿足的
                                    //下一個要查找的索引和單詞大小相等說明，
                                    //word的0 - index的位置的字母已經匹配
            return true;
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) //不可越界
            return false;
        if(visited[x][y]) //如果之前訪問過，那麼直接返回false
            return false;
        if(board[x][y] != word[index]) //不相等，這條路走不通，剪枝
            return false;
        visited[x][y] = true; //先標記為走過，因為下一次會走向四個方向
        bool ret = dfs(board, word, index + 1, x, y + 1, visited) ||
                dfs(board, word, index + 1, x, y - 1, visited)    ||
                dfs(board, word, index + 1, x - 1, y, visited)     || 
                dfs(board, word, index + 1, x + 1, y, visited); 
        visited[x][y] = false;  //走過之後，不過不匹配，要還原為沒有走過
        return ret;
    }
};