- Leetcode 3568. Minimum Moves to Clean the Classroom
- 1. 解題思路
- 2. 代碼實現
- 題目鏈接：3568. Minimum Moves to Clean the Classroom
1. 解題思路
這一題我的核心思路就是廣度優先遍歷遍歷+剪枝。
顯然，我們可以給出一個廣度優先遍歷來給出所有可能的走法直至無法繼續或者撿完所有垃圾。
但是，上述情況事實上可能會無限循環下去，而且所有的走法也非常浪費，因此，我們需要對其進行剪枝，從而優化我們的計算。
而這里，我的剪枝思路就是：
- 如果一個點曾經走過，則當他重新回到這個點的時候，他必須滿足以下兩個條件之一，否則這條路線必然不會是最優的，可以直接忽略：
- 他在中間的過程中撿過了新的垃圾；
- 他在中間的過程中補充了能量（即回來時的能量值大于之前來的時候的能量值）
由此，我們就能對上述問題進行解答了。
2. 代碼實現
給出python代碼實現如下：
class Solution:def minMoves(self, classroom: List[str], energy: int) -> int:n, m = len(classroom), len(classroom[0])k, mapping, seen = 0, {}, {}for i in range(n):for j in range(m):if classroom[i][j] == "L":mapping[(i, j)] = kk += 1elif classroom[i][j] == "S":start = (0, 0, -energy, i, j)seen[(0, i, j)] = energyif k == 0:return 0q = [start]while q:step, status, e, i, j = heapq.heappop(q)status = -statuse = -eif status == (2**k)-1:return stepelif e <= 0:continueif i-1 >= 0 and classroom[i-1][j] != "X":new_status = status if classroom[i-1][j] != "L" else status | (1 << mapping[(i-1, j)])new_energy = e-1 if classroom[i-1][j] != "R" else energyif seen.get((new_status, i-1, j), -1) < new_energy:heapq.heappush(q, (step+1, -new_status, -new_energy, i-1, j))seen[(new_status, i-1, j)] = new_energyif i+1 < n and classroom[i+1][j] != "X":new_status = status if classroom[i+1][j] != "L" else status | (1 << mapping[(i+1, j)])new_energy = e-1 if classroom[i+1][j] != "R" else energyif seen.get((new_status, i+1, j), -1) < new_energy:heapq.heappush(q, (step+1, -new_status, -new_energy, i+1, j))seen[(new_status, i+1, j)] = new_energyif j-1 >= 0 and classroom[i][j-1] != "X":new_status = status if classroom[i][j-1] != "L" else status | (1 << mapping[(i, j-1)])new_energy = e-1 if classroom[i][j-1] != "R" else energyif seen.get((new_status, i, j-1), -1) < new_energy:heapq.heappush(q, (step+1, -new_status, -new_energy, i, j-1))seen[(new_status, i, j-1)] = new_energyif j+1 < m and classroom[i][j+1] != "X":new_status = status if classroom[i][j+1] != "L" else status | (1 << mapping[(i, j+1)])new_energy = e-1 if classroom[i][j+1] != "R" else energyif seen.get((new_status, i, j+1), -1) < new_energy:heapq.heappush(q, (step+1, -new_status, -new_energy, i, j+1))seen[(new_status, i, j+1)] = new_energyreturn -1
提交代碼評測得到：耗時3097ms，占用內存58.28MB。
