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

int Dir[4][2]={
  {0,1},{0,-1},{1,0},{-1,0}};class Solution {//DFS Find the pathpublic:		void DFS(int curX, int curY, int curPos, vector
   
    
     >& visit, 		bool& OK, vector
     
      
       > &board, string& word )	{		if(OK) return;		if(word[curPos] != board[curX][curY]) return;		if(curPos == word.size()-1)		{			OK = true;			return;		}		for (int d = 0; d < 4; ++d)		{			int nextX = curX+Dir[d][0];			int nextY = curY+Dir[d][1];			if(nextX >= 0 && nextX < board.size() && nextY >= 0 && nextY < board[0].size())			{				if(!visit[nextX][nextY])				{					visit[nextX][nextY] = true;					DFS(nextX, nextY, curPos+1, visit, OK, board, word);					visit[nextX][nextY] = false;				}			}		}	}public:	bool exist(vector
       
        
          > &board, string word) { // Start typing your C/C++ solution below // DO NOT write int main() function if(word.size() == 0) return false; if(board.size() == 0 || board[0].size() == 0) return false; bool OK = false; vector
         
          
           > visit(board.size(), vector
           
            (board[0].size(), false)); for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[i].size(); ++j) { visit[i][j] = true; DFS(i, j, 0, visit, OK, board, word); visit[i][j] = false; if(OK) return true; } } return false; }};
           
          
         
        
       
      
     
    
   

second time

class Solution {public:    int dir[4][2] = {
  {-1, 0}, {1, 0}, {0, -1}, {0, 1}};    bool findPath(vector
   
    
      > &board, string& word, vector
     
      
        >& used, int curX, int curY, int curIdx)    {        int n = board.size();        int m = board[curX].size();        if(curIdx == word.size()) return true;        for(int k = 0; k < 4; ++k)        {            int newX = curX+dir[k][0];            int newY = curY+dir[k][1];            if(newX >= 0 && newX < n && newY >= 0 && newY < m && used[newX][newY] == false && board[newX][newY] == word[curIdx])            {                used[newX][newY] = true;                if(findPath(board, word, used, newX, newY, curIdx+1)) return true;                used[newX][newY] = false;            }        }        return false;    }    bool exist(vector
       
        
          > &board, string word) { // Start typing your C/C++ solution below // DO NOT write int main() function if(word.size() == 0) return true; int n = board.size(); if(n == 0) return false; int m = board[0].size(); vector
         
          
            > used(n, vector
           
            (n, false)); for(int i = 0; i < board.size(); ++i) { for(int j = 0; j < board[i].size(); ++j) { if(board[i][j] == word[0]) { used[i][j] = true; if(findPath(board, word, used, i, j, 1)) return true; used[i][j] = false; } } } return false; }};
           
          
         
        
       
      
     
    
   

转载地址：http://mhxti.baihongyu.com/