在矩阵中搜索单词

DFS(注意dfs函数中需要通过或运算进行剪枝，否则会超时)：

//
// Created by jt on 2020/9/24.
//
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char> > &board, string word) {
        if (board.size() < 1) return false;
        vector<vector<int> > visited(board.size(), vector<int>(board[0].size(), 0));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (dfs(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<vector<char> > &board, string &word, int pos, int x, int y,
            vector<vector<int> > &visited) {
        if (pos == word.size()) return true;
        if (x < 0 || x > board.size()-1 || y < 0 || y > board[0].size()-1) return false;
        if (visited[x][y]) return false;
        if (board[x][y] != word[pos]) return false;
        visited[x][y] = 1;
        // 通过合并或运算剪枝
        bool a = dfs(board, word, pos+1, x-1, y, visited) ||
                 dfs(board, word, pos+1, x+1, y, visited) ||
                 dfs(board, word, pos+1, x, y-1, visited) ||
                 dfs(board, word, pos+1, x, y+1, visited);
        visited[x][y] = 0;
        return a;
    }
};