1、题目

https://leetcode-cn.com/problems/word-search/

2、题意

题解1：递归回溯
ps：将走过的点标记为’.’ 进行特判 以免其重复走

class Solution {
public:int dx[4] = {0,0,1,-1},dy[4] = {1,-1,0,0};bool dfs(vector<vector<char>>& board, string& word,int now,int x,int y){if(board[x][y]!=word[now]) return false;if(now==word.size()-1)return true;char t = board[x][y];board[x][y] = '.';for(int i=0;i<4;i++){int m = x+dx[i],n = y+dy[i];if(m<0||n<0||m>=board.size()||n>=board[0].size()||board[m][n]=='.') continue;if(dfs(board,word,now+1,m,n))return true;}board[x][y] = t;return false;}bool exist(vector<vector<char>>& board, string word) {for(int i=0;i<board.size();i++)for(int j=0;j<board[0].size();j++)if(board[i][j]==word[0]&&dfs(board,word,0,i,j))return true;return false;}
};