The problem
A grid is given as a list of strings: '.' is an open square and '#' is a wall. Start on the top-left square and reach the bottom-right square. Each move goes one square up, down, left or right, and stays inside the grid. You may move onto at most k wall squares in total. Return the fewest moves, or -1 if the end cannot be reached.
grid = ['..#.',
'#.#.',
'..#.',
'.##.']
fewest_moves(grid, 1) # 6
fewest_moves(grid, 0) # -1
The top-left and bottom-right squares are always open.
Limits
- Up to 200 × 200 squares, and
kup to 400. - Trying every route is far too slow. The two big tests with walls to break have 4 seconds each.
Builds on GRPH-7 Grids as graphs.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | No walls to break | Not run | |
| 3 | One square | Not run | |
| 4 | A row of walls | Not run | |
| 5 | Not enough breaks | Not run | |
| 6 | One visit per square is not enough | Not run | |
| 7 | A wall saves many moves | Not run | |
| 8 | Breaks to spare | Not run | |
| 9 | 40 × 40 | Not run | |
| 10 | 200 × 200, k = 0 | Not run | |
| 11 | 200 × 200, k = 3 | Not run | |
| 12 | Walls everywhere | Not run |