首页 > 其他 > 详细

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

时间:2022-05-27 22:54:32      阅读:15      评论:0      收藏:0      [点我收藏+]

在矩阵中进行搜索,是选择能够到达的点,而不是仅仅选择符合要求(数位之和小于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 };

 

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

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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!