剑指 Offer 13. 机器人的运动范围

时间：2022-05-27 22:54:32 收藏：0 阅读：17

在矩阵中进行搜索，是选择能够到达的点，而不是仅仅选择符合要求（数位之和小于k）的点。例如，当k = 3，[0,9]点并不能到达，但是[0, 10]点却符合要求，所以这个点就不可以使用。

但还要找到虽然当前路径时不能到达的点，通过后续遍历就可以到达了，所以还是需要进行遍历搜索。因为一个符合要求的点当前路径无法达到时，通过遍历，总会有一条路径可以达到，且因为这个点符合要求，所以一定会将这个点遍历进去。

方法一 DFS

 1 /**
 2  * @param {number} m
 3  * @param {number} n
 4  * @param {number} k
 5  * @return {number}
 6  */
 7 var movingCount = function(m, n, k) {
 8     //dfs
 9     let visited = Array(m).fill().map(x => Array(n).fill(false));
10     let dfs = (row, colom, sum_1, sum_2) => {
11         if(row >= m || colom >= n || sum_1 + sum_2 > k || visited[row][colom]) {
12             return 0;
13         }
14         visited[row][colom] = true;
15         return 1 
16         + dfs(row + 1, colom, (row + 1) % 10 == 0 ? sum_1 - 8 : sum_1 + 1, sum_2) 
17         + dfs(row, colom + 1, sum_1, (colom + 1) % 10 == 0 ? sum_2 - 8 : sum_2 + 1);
18     }
19     return dfs(0, 0, 0, 0);
20 };

方法二 BFS

 1 /**
 2  * @param {number} m
 3  * @param {number} n
 4  * @param {number} k
 5  * @return {number}
 6  */
 7 var movingCount = function(m, n, k) {
 8     //bfs
 9     let visited = Array(m).fill().map(x => Array(n).fill(false));
10     let queue = [[0, 0, 0, 0]], res = 0;
11     while(queue.length > 0) {
12         const [row, colom, sum_1, sum_2] = queue.shift();
13         if(row >= m || colom >= n || sum_1 + sum_2 > k || visited[row][colom]) {
14             continue;
15         }
16         visited[row][colom] = true;
17         res++;
18         queue.push([row + 1, colom, (row + 1) % 10 == 0 ? sum_1 - 8 : sum_1 + 1, sum_2]);
19         queue.push([row, colom + 1, sum_1, (colom + 1) % 10 == 0 ? sum_2 - 8 : sum_2 + 1]);
20     }
21     return res;
22 };

原文：https://www.cnblogs.com/yukinon/p/15336254.html