本文共 1092 字，大约阅读时间需要 3 分钟。

题目描述

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

来源：力扣（LeetCode）

C++

class Solution {
   public: //直觉:深度优先遍历。每个点为单词起点，进行上下左右的深度搜搜。    bool exist(vector
   
    
     >& board, string word) {
           vector
     
      
       > visited(board.size(),vector
       
        (board[0].size(),false));//标注是否被访问过        for(int i=0;i
        
         > &board,string & word,int row,int col,int index, vector
         
          
           > &visited){ //row,col是棋盘的当前位置；index是单词的当前位置 int m=board.size(); int n=board[0].size(); int len=word.size(); //越界、已经访问过，值不相等就返回 if(row<0 || row>=m || col<0 ||col>=n|| visited[row][col] || board[row][col]!=word[index]) { return false; } visited[row][col]=true; index++; if(index==word.size()||dfs(board,word,row+1,col,index,visited)|| dfs(board,word,row-1,col,index,visited)||dfs(board,word,row,col+1,index,visited)||dfs(board,word,row,col-1,index,visited)) return true; visited[row][col]=false; return false; }};