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 算法之前，为提升计算效率，首先讲述两项前置工作： 数位之和计算 、 搜索方向简化 。
因此，可通过循环求得数位和 s。
图例展示了 n,m = 20n,m=20 ， k \in [6, 19]k∈[6,19] 的可达解、不可达解、非解，以及连通性的变化。
方法一：深度优先遍历 DFS
算法解析：
① 行列索引越界
② 数位和超出目标值 k
③ 当前元素已访问过 时，返回 0，代表不计入可达解。
标记当前单元格 ：将索引 (i, j) 存入 Set visited 中，代表此单元格已被访问过。
搜索下一单元格： 计算当前元素的 下、右 两个方向元素的数位和，并开启下层递归 。
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 实现： 通常利用队列实现广度优先遍历。
算法解析：
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 }
原文：https://www.cnblogs.com/sbb-first-blog/p/13584096.html