79.单词搜索

题目
给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

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

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

思路
使用DFS遍历矩阵，直到遍历完字符串，说明匹配。但是需要记录矩阵中哪个字符是已经匹配过的。

由于英文字符范围是0~127，因此遍历某个字符后，进行c^=128操作，该字符在后续匹配中就不会再次匹配到，从而实现标记的效果。在回溯的时候需要将标记的字符还原。

#include<vector>
using namespace std;
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int rows = board.size(), cols = board[0].size();
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (findWord(board, word, i, j, 0))
                    return true;
            }
        }
        return false;
    }
    bool findWord(vector<vector<char>> board, string word, int row, int col, int index)
    {
        if (index == word.size()) return true;
        if (row < 0 || col < 0 || row >= board.size() || col >= board[0].size() || board[row][col] != word.at(index))
            return false;
        board[row][col] ^= 128;
        bool exist = findWord(board, word, row - 1, col, index + 1) ||
                     findWord(board, word, row, col - 1, index + 1) ||
                     findWord(board, word, row + 1, col, index + 1) ||
                     findWord(board, word, row, col + 1, index + 1);
        board[row][col] ^= 128;
        return exist;
    }
};

int main(int argc, char* argv[])
{
    vector<vector<char>> test = { 
        { 'A','B','C','E' }, 
        { 'S','F','C','S' }, 
        { 'A','D','E','E' } };
    vector<vector<char>> test2 = {
        { 'A' },
        { 'B'} };
    string word1 = "ABCCED", word2 = "SEE", word3 = "BA";

    auto res = Solution().exist(test2, word3);
    return 0;
}