福州网络营销网站,做网站购买服务器多少钱,徐州seo全网营销,seo优化案例Leetcode 2850. Minimum Moves to Spread Stones Over Grid 1. 算法思路2. 代码实现 题目链接#xff1a;2850. Minimum Moves to Spread Stones Over Grid
1. 算法思路
这一题由于棋盘比较小#xff0c;只是一个3x3的棋盘#xff0c;所有的移动策略总量有限#xff0c;…Leetcode 2850. Minimum Moves to Spread Stones Over Grid 1. 算法思路2. 代码实现 题目链接2850. Minimum Moves to Spread Stones Over Grid
1. 算法思路
这一题由于棋盘比较小只是一个3x3的棋盘所有的移动策略总量有限因此这里我们直接的一个思路就是使用一个深度优先遍历来考察所有可能的移动策略然后从中取出move总数最小的一种方案对应的结果。
2. 代码实现
给出python代码实现如下
class Solution:def minimumMoves(self, grid: List[List[int]]) - int:_from [0 for _ in range(9)]_to [0 for _ in range(9)]for i in range(3):for j in range(3):idx i * 3 jif grid[i][j] 0:_to[idx] 1elif grid[i][j] 1:_from[idx] grid[i][j] - 1def cal_distance(i, j):r1, c1 i//3, i%3r2, c2 j//3, j%3return abs(r1-r2) abs(c1-c2)def dfs(idx):if idx 9:return 0if _from[idx] 0:return dfs(idx1)res math.inf_from[idx] - 1for i in range(9):if _to[i] 0:continue_to[i] 0res min(res, cal_distance(idx, i) dfs(idx))_to[i] 1_from[idx] 1return resreturn dfs(0)提交代码评测得到1171ms占用内存16.4MB。
