79. 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.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Constraints:

• board and word consists only of lowercase and uppercase English letters.
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

---

给定一个字符面板和一个单词，问能否在该面板中搜索到该单词，搜索路径只能水平或垂直。 简单的深度搜索题，首先找到第一个字符的起始位置，然后深度往该字符的上下左右搜，只要有一个true就返回true，否则重置标记位，返回false。 完整代码如下：

class Solution {
private:
    bool dfs(vector<vector<char> >& board, vector<vector<char> >& mark, int row, int col, string& word, int step)
    {
        if (board[row][col] != word[step])
            return false;
        if (step == word.size() – 1)
            return true;
        mark[row][col] = 1;
        if (row – 1 >= 0 && mark[row – 1][col] == 0) {
            bool ans = dfs(board, mark, row – 1, col, word, step + 1);
            if (ans)
                return true;
        }
        if (row + 1 < board.size() && mark[row + 1][col] == 0) {
            bool ans = dfs(board, mark, row + 1, col, word, step + 1);
            if (ans)
                return true;
        }
        if (col – 1 >= 0 && mark[row][col – 1] == 0) {
            bool ans = dfs(board, mark, row, col – 1, word, step + 1);
            if (ans)
                return true;
        }
        if (col + 1 < board[0].size() && mark[row][col + 1] == 0) {
            bool ans = dfs(board, mark, row, col + 1, word, step + 1);
            if (ans)
                return true;
        }
        mark[row][col] = 0;
        return false;
    }
public:
    bool exist(vector<vector<char> >& board, string word)
    {
        if (word.size() == 0)
            return true;
        int m = board.size();
        if (m == 0)
            return false;
        int n = board[0].size();
        if (n == 0)
            return false;
        vector<vector<char> > mark(m, vector<char>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == word[0] && dfs(board, mark, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }
};

本代码提交AC，用时9MS，击败95.63%的人。