The state that actually matters here is a triple: which cell I stand on, which litter I've already grabbed, and how much energy is still in the tank. Every move costs one step, so a breadth-first search over those states hands me the minimum move count directly. The only twist is that stepping onto an `R` cell refuels me to the maximum, so the same cell-and-collected-set can be worth revisiting when I arrive with more energy. My first instinct was to reduce it to a Traveling-Salesman over the litter cells: precompute shortest distances between every pair of `L` cells plus the start, then try every visiting order. That quietly computes the wrong graph. The energy cap and the reset cells make pairwise distances dependent on each other -- how cheaply I can go from one litter to the next depends on how much fuel I arrived with and which `R` I can detour through -- so there is no fixed distance to feed the TSP. ## Key idea Run BFS over the state `(row, col, mask, energy)`. From a state with energy `e > 0`, each of the four neighbors costs one move and drops energy to `e - 1`; if that neighbor is an `R`, the energy snaps back to the maximum instead. Landing on an `L` sets its bit in `mask`. The first time BFS pops a state whose `mask` is all-ones, that layer's distance is the answer. What keeps this from exploding is domination. For a fixed `(row, col, mask)`, if I already reached it with energy `e0` at an earlier or equal distance, then any later arrival carrying energy `e <= e0` is worthless -- fewer moves and more fuel both only help, and the earlier state already wins on both. So I store one number `best[row][col][mask]` = the most energy ever seen there, and I enqueue an arrival only when its energy strictly beats that. Each `(row, col, mask)` then expands a handful of times rather than once per possible energy level. ### Worked example Take `classroom = ["LS", "RL"]` with `energy = 4`. I start at `(0, 1)` holding 4 fuel and `mask = 00`. Step left to `(0, 0)` and grab the first litter: `mask = 01`, energy 3. Step down to `(1, 0)`, an `R`, so energy resets to 4 while `mask` stays `01`. Step right to `(1, 1)` and grab the second litter: `mask = 11`, all collected in 3 moves. No route reaches both litters in fewer, so the answer is 3. ### Complexity Time is `O(m * n * 2^k * k)` with `k <= 10` the litter count: each of the `m * n * 2^k` states expands only a small number of times and scans 4 neighbors. Space is `O(m * n * 2^k)` for the `best` table. ### Code (C++) ```cpp class Solution { public: int minMoves(vector& classroom, int energy) { int m = classroom.size(), n = classroom[0].size(); int sr = 0, sc = 0; vector> litter; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { char ch = classroom[i][j]; if (ch == 'S') { sr = i; sc = j; } else if (ch == 'L') litter.push_back({i, j}); } int K = litter.size(); int full = (1 << K) - 1; if (full == 0) return 0; vector> lidx(m, vector(n, -1)); for (int k = 0; k < K; k++) lidx[litter[k].first][litter[k].second] = k; int S = 1 << K; vector best((long)m * n * S, -1); auto id = [&](int r, int c, int mask) { return ((long)r * n + c) * S + mask; }; best[id(sr, sc, 0)] = energy; queue> q; q.push({sr, sc, 0, energy}); int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1}; int dist = 0; while (!q.empty()) { int sz = q.size(); for (int s = 0; s < sz; s++) { auto cur = q.front(); q.pop(); int r = cur[0], c = cur[1], mask = cur[2], e = cur[3]; if (mask == full) return dist; if (e < best[id(r, c, mask)]) continue; if (e <= 0) continue; for (int d = 0; d < 4; d++) { int nr = r + dr[d], nc = c + dc[d]; if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue; char ch = classroom[nr][nc]; if (ch == 'X') continue; int ne = e - 1; int nmask = mask; if (ch == 'L') nmask |= (1 << lidx[nr][nc]); if (ch == 'R') ne = energy; long ii = id(nr, nc, nmask); if (ne > best[ii]) { best[ii] = ne; q.push({nr, nc, nmask, ne}); } } } dist++; } return -1; } }; ``` ### One note The ordering that actually bites is when the reset applies. You need `e >= 1` before a move, and the `R` refuel happens after you step onto the cell -- so a move that lands on `R` with `e = 1` is legal and refills you, while the identical move onto a normal cell dead-ends at `e = 0`. I compute `ne = e - 1` first and only then override it with the reset, which keeps that whole rule in a single spot.