DFS BFS搜索算法经常带有一个visited矩阵
DFS算法入口一般传入第一轮位置参数，就像树遍历传入root根节点一样，然后每一轮DFS（每一层递归）就调用DFS（参数位置+1）（即下一个位置，具体不一定要这样）
其涵盖拥有前面递归所说的一切经验：理解子问题，思考齐全①递归出口（所有终止条件）、②递归入栈（如何继续递归）与③执行体（做什么操作）（①和②可以合并在一起，不符合条件不继续递归，自然出栈）
经常需要使用全局变量来记录递归中的参数
对于DFS，要有子问题思维：以前、以后的问题是不可见的，现在只需要考虑当前该节点的小问题，当前结点拥有哪些变量
也要有全局思维：理清子问题与以前、以后问题的关系
回溯返回值可以跨越递归层级进行各种信息（当然得当前结点看得见的）传递
对于BFS问题，有两个关键：出队的时候执行执行体，入队的时候判断是否入队（这两者可以在一起，即入队就是上层出队结点的执行体）
队列为空则遍历结束
DFS的关键：①入口与出口 ②【单线程执行】（进栈出栈顺序），回溯（同层多入口。同层多入口间要回溯以免同层其它递归路径的影响）
结点搜索问题：机器人的运动范围
核心问题：
遍历到符合要求的结点就全局计数，路径走不通就返回
注意是搜索符合要求的结点
(DFS)思路：维持一个全局计数矩阵，DFS中走到死路直接该条递归路径出口
(BFS)思路：在BFS中走到死路不入队
问题：
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
注意：①是要能够走到的格子
②求的是位和
解答：
DFS解法
class Solution { //标记矩阵 boolean[][] visited; int count = 0; public int movingCount(int m, int n, int k) { visited = new boolean[m][n]; //init visited array for(int i=0;i<m;i++) for(int j=0;j<n;j++) visited[i][j] = false; //开始dfs dfs(0,0,m,n,k); return count; } public void dfs(int x,int y,int m,int n,int k) { //出口条件 //注意边界条件，题目中写的是0~m-1,0~n-1走，不能走到n if(x>m-1 || y>n-1 || (x/10+x%10+y/10+y%10)>k || visited[x][y]==true) return ; //执行体 count++; visited[x][y] = true; //递归入栈 dfs(x,y+1,m,n,k); dfs(x+1,y,m,n,k); } }BFS解法
class Solution { boolean[][] visited; int count = 0; public int movingCount(int m, int n, int k) { visited = new boolean[m][n]; //init visited array for(int i=0;i<m;i++) for(int j=0;j<n;j++) visited[i][j] = false; //开始bfs;注意这里将坐标以一个数组的形式记录入队 Queue<Integer[]> qe = new LinkedList(); qe.add(new Integer[]{0,0}); while(!qe.isEmpty()) { //出栈，执行体 Integer[] pos = qe.remove(); //【这里判断本层结点是否执行执行体：计数count+1】 if ((pos[0]/10+pos[0]%10+pos[1]/10+pos[1]%10)<=k && visited[pos[0]][pos[1]]==false) { count++; visited[pos[0]][pos[1]] = true; //【本层结点能执行说明路没被堵，这才判断相邻下一层结点是否入队；所以要放进外层if执行体里】 if (pos[0]<m && pos[1]+1<n) qe.add(new Integer[]{pos[0],pos[1]+1}); if (pos[0]+1<m && pos[1]<n) qe.add(new Integer[]{pos[0]+1,pos[1]}); } } return count; } }本题DFS比BFS快13倍
字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例：
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]解答：
import java.util.*;
class Solution {
List<String> res = new LinkedList<>();
//用来缓存得到的搜索路径
char[] c;
String[] permutation(String s)
{
//转化为字符数组
c = s.toCharArray();
dfs(0);
return res.toArray(new String[0]); //注意，传入的这个参数表明array元素的类型，必须是一个对象
}
//每次递归的路径该怎么记录：因为【用的是交换来固定元素以确定路径】当一堆交换，那么字符串本身就是结果！
void dfs(int x)
{
//dfs到最后一位了，这时候已经通过交换确定了一个搜索路径了。所以即为c本身（一个序列）
if (x==c.length-1)
{
res.add(String.valueOf(c));
return ;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < c.length; i++)
{
//使用hashset判断要交换的i位是不是重复元素（字符串中可能含有重复元素），避免【同层】重复搜索
if (set.contains(c[i]))
continue;
set.add(c[i]);
//将x与i位交换
swap(x,i);
dfs(x+1);
//注意要换回来，因为这是同一轮（同一个位置）下，为了下一次固定数选其他位置交换要先还原
swap(x,i);
}
}
void swap(int a,int b)
{
char temp = c[a];
c[a] = c[b];
c[b] = temp;
}
public static void main(String[] args)
{
Solution sol = new Solution();
String[] solution = sol.permutation(args[0]);
Arrays.sort(solution);
System.out.print("["+solution[0]);
for (int i=1;i<solution.length;i++)
System.out.print(","+solution[i]);
System.out.print("]");
}
}路径搜索问题：寻找某个路径
核心问题：
遍历符合要求的路径才计数，路径走不通就返回
即整条递归路径（栈）符合要求才计数
思路：通过回溯返回值来标记符合要求的路径，当只要递归路径中所有结点全满足要求才返回满足要求
即通过返回值来标记该节点后面的所有节点组成的问题（递归子问题）是否满足要求
问题：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[[“a”,”b“,”c”,”e”],
[“s”,”f“,”c“,”s”],
[“a”,”d”,”e“,”e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false提示：
1 <= board.length <= 200
1 <= board[i].length <= 200
解答：
递归参数：坐标位置x,y，当前目标字符在字符串word中的索引
终止条件：①行列位置越界 或②当前矩阵元素与目标字符不同 或③当前矩阵已经访问过
P.S.注意由于可以从任何一个位置开始dfs，那么就有多个dfs过程，所以不能直接使用全局visited矩阵，但是如果使用局部visited矩阵，那每一次递归栈里都有一个visited矩阵，储存开销/时间开销巨大！
所以如果我们要使用全局的形式就需要每一次return就还原visited当前值矩阵！（看代码中“注意visited矩阵的处理”那段，进栈标记，以防子问题走到已经访问过的格子，出栈复原）
public class Offer12
{
static boolean[][] visited;
public static boolean exist(char[][] board,String word)
{
visited = new boolean[board.length][board.length];
//每一个格子都可以是起点，对于每一个格子起点的dfs都有一个visited矩阵
for(int i=0;i<board.length;i++)
for(int j=0;j<board.length;j++)
//以i,j为起点开始dfs
if(dfs(board,word,i,j,0))
return true;
return false;
}
public static boolean dfs(char[][] board,String word,int x,int y,int nowPointer)
{
//退出条件：①单元格撞墙或②单元格的内容与字符串索引位不匹配或③访问过
if(x<0 || y<0 || x>=board.length || y>=board.length || board[x][y]!=word.charAt(nowPointer) || visited[x][y]==true)
return false;
//退出条件：遍历到字符串最后一个
if(nowPointer==word.length()-1)
return true;
//回溯返回值：当前结点所有子问题如果有一条路可行（返回true）那就是true
//递归入口：即探访子问题——可以向上下左右四个方向走
//注意visited矩阵的处理，进栈流程中要标记为true，出栈流程中要复原回去
visited[x][y] = true;
boolean res = dfs(board,word,x+1,y,nowPointer+1) ||
dfs(board,word,x-1,y,nowPointer+1) ||
dfs(board,word,x,y+1,nowPointer+1) ||
dfs(board,word,x,y-1,nowPointer+1);
//出栈复原
visited[x][y] = false;
return res;
}
public static void main(String[] args)
{
char[][] board = new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
String word = "ABCCED";
System.out.println(exist(board,word));
}
}
---
true 路径记录问题：迷宫问题
在DFS的同时还需要记录DFS的搜索路径：使用一个list或stack保存路径！
具体地，出栈的时候，如果满足要求，就将该节点保存下来（入list或stack）
如果要保存多个路径：每次传递的时候就逐层累计记录下来已经走下的路径，走到终点判断该路可以就记录该累计变量or打印
变种：打印符合某条件的路径（一样的思路）
回溯返回值问题：树的深度
思路：
回溯返回值除了可以用于寻找满足条件的递归路径，还可以做很多事情，只要抓住一点，回溯返回值可以传递递归不同层级当前结点看得到的各种信息
树的深度其实就是求最长递归路径
解答：
注意观察路径记录问题和回溯返回值问题
路径记录问题，越往下递归路径越多，所以我们得前序遍历，递归到一个节点就执行执行体（记录该路径点）
回溯返回值问题，我们是要比较左右子树符合条件的路径，最终我们只要一条路径，所以得后序遍历，递归返回的时候才执行执行体（比较左右子树最深那个，返回深度值）
注意区别递归顺序和执行顺序
