穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞单词搜索

题目：

解析

决策树：

代码设计：

代码：

class Solution {private boolean[][] visit;//标记使用过的数据int m,n;//行，列char[] word;public boolean exist(char[][] board, String _word) {m = board.length;n = board[0].length;visit = new boolean[m][n];word = _word.toCharArray();for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(word[0] == board[i][j]){visit[i][j] = true;if(dfs(board,i,j,1)) return true;visit[i][j] = false;//恢复现场}}return false;    }int[] dx = {0,0,-1,1};int[] dy = {-1,1,0,0};boolean dfs(char[][]board, int i, int j, int pos){if(pos == word.length){return true;//搜索成功}for(int k = 0; k < 4; k++) {int x = i + dx[k]; int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && word[pos] == board[x][y]){visit[x][y] = true;if(dfs(board,x,y,pos+1)) return true;visit[x][y] = false;//恢复现场}}return false;}
}