BFS和DFS---------机器人的运动范围

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/mian-shi-ti-13-ji-qi-ren-de-yun-dong-fan-wei-dfs-b/

解题思路：
本题与矩阵中的路径类似，是典型的矩阵搜索问题。此类问题通常可使用深度优先搜索（DFS）或广度优先搜索（BFS）解决。在介绍 DFS / BFS 算法之前，为提升计算效率，首先讲述两项前置工作：数位之和计算、搜索方向简化。

因此，可通过循环求得数位和

图例展示了

方法一：深度优先遍历 DFS

深度优先搜索：可以理解为暴力法模拟机器人在矩阵中的所有路径。DFS 通过递归，先朝一个方向搜到底，再回溯至上个节点，沿另一个方向搜索，以此类推。
剪枝：在搜索中，遇到数位和超出目标值、此元素已访问，则应立即返回，称之为可行性剪枝。

算法解析：

递归参数：当前元素在矩阵中的行列索引 i 和 j ，两者的数位和 si, sj 。
终止条件：当

　　　　① 行列索引越界

　　　　② 数位和超出目标值 k

　　　　③ 当前元素已访问过时，返回 0，代表不计入可达解。

递推工作：

　　　　标记当前单元格 ：将索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。

　　　　搜索下一单元格：计算当前元素的下、右两个方向元素的数位和，并开启下层递归。

回溯返回值：返回 1 + 右方搜索的可达解总数 + 下方搜索的可达解总数，代表从本单元格递归搜索的可达解总数。

 1 int dfs(int m,int n,int k,int i,int j,int visited[m][n])
 2 {
 3 
 4     if(i<0||i==m||j<0||j==n||visited[i][j]==1||i%10+i/10+j%10+j/10>k)
 5     {
 6         return 0;
 7     }
 8     visited[i][j]=1;
 9     return dfs(m,n,k,i+1,j,visited)+dfs(m,n,k,i,j+1,visited)+1;
10 }
11 int movingCount(int m, int n, int k){
12     int visited[m][n];
13     memset(visited, 0, m * n * sizeof(int));
14     int ans=dfs(m,n,k,0,0,visited);
15     return ans;
16 }

方法二：广度优先遍历 BFS
BFS/DFS ： 两者目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式向前搜索。
BFS 实现： 通常利用队列实现广度优先遍历。
算法解析：

初始化： 将机器人初始点 (0, 0)(0,0) 加入队列 queue ；
迭代终止条件： queue 为空。代表已遍历完所有可达解。
迭代工作：

单元格出队：将队首单元格的索引、数位和弹出，作为当前搜索单元格。
判断是否跳过：若 ① 行列索引越界或 ② 数位和超出目标值 k 或 ③ 当前元素已访问过时，执行 continue 。
标记当前单元格：将单元格索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
单元格入队：将当前元素的下方、右方单元格的索引、数位和加入 queue 。

返回值： Set visited 的长度 len(visited) ，即可达解的数量。

 1 int movingCount(int m,int n,int k)
 2 {
 3     int ans=0;
 4     int queue[m*n][2];
 5     int head=-1,tail=-1;    //在后续操作中，head指向的位置的元素已出队
 6     int visited[m][n];
 7     memset(visited,0,m*n*sizeof(int));
 8     tail++;
 9     //初始化
10     queue[tail][0]=0;       //存放坐标[0,0]
11     queue[tail][1]=0;
12     //迭代工作
13     while(head!=tail)          //迭代中止条件，queue为空，代表已遍历完所有的可达解
14     {
15         //单元格出队
16         head++;
17         int r=queue[head%(m*n)][0];   //对行进行操作
18         int c=queue[head%(m*n)][1];   //对列进行操作
19         //判断是否跳过，若是则执行continue
20         if(r<0||r==m||c<0||c==n||visited[r][c]==1||r%10+r/10+c%10+c/10>k)
21         {
22            continue;
23         }
24         ans++;
25         //标记当前单元格
26         visited[r][c]=1;              //对单元格进行标记
27         //单元格入队
28         tail++;
29         queue[tail%(m*n)][0]=r+1;
30         queue[tail%(m*n)][1]=c;
31         tail++;
32         queue[tail%(m*n)][0]=r;
33         queue[tail%(m*n)][1]=c+1;
34     }
35     return ans;
36 }