本文主要是介绍LintCode 873. 模拟松鼠 JavaScript算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
描述
给定一个二维网格, 其中有一棵树, 一个松鼠和几枚坚果. 松鼠同一时间内最多只能携带一枚坚果. 松鼠可以向上, 下, 左, 右的相邻的方格移动.
请问, 松鼠要把所有的坚果送到树下, 最少需要移动多少格距离.
说明
- 所有给定的位置都不会重叠.
- 松鼠一次最多只能携带一枚坚果.
- 给定的坚果位置没有顺序.
- 高度和宽度是正整数。3 <= 高度 * 宽度 <= 10,000.
- 给定的网格中至少包含一个坚果, 同时只有一棵树和一只松鼠.
样例
- 样例 1:输入: height = 5, width = 7,treePosition = [2, 2],squirrelPosition = [4, 4],nuts = [[3, 0], [2, 5]]
输出: 12- 样例 2:输入: height = 1, width = 3,treePosition = [0,1],squirrelPosition = [0,0],nuts = [[0,2]]
输出: 3
解析
const minDistance = (height, width, tree, squirrel, nuts) => {let res = 0;let rows = nuts.length;let dist1, dist2, dist3, dist4, tag, index;const L = (a, b) => Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1])for(let i = 0; i < rows; i++) {tag = 1;index = i;for(let j = i + 1; j < rows; j++) {dist1 = L(nuts[i], squirrel);dist2 = L(nuts[i], tree);dist3 = L(nuts[j], squirrel);dist4 = L(nuts[j], tree);if(dist1 + dist4 > dist3 + dist2) {tag = 0;break;}}if(tag || i == rows - 1) break;}for(i = 0; i < rows; i++) {if(i == index) { res += L(nuts[i], squirrel) + L(nuts[i], tree) }else res += 2 * L(nuts[i], tree)}return res;
}
运行结果
这篇关于LintCode 873. 模拟松鼠 JavaScript算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!