The Cheapest Walk Across a Toll Grid
Solve this ProblemYou are given a grid of positive costs. Starting on the top-left cell, walk up, down, left or right to reach the bottom-right cell, paying the value of every cell you enter (including the start). Find the smallest total cost.
Because the cheapest walk may go away from the goal to avoid expensive cells, a dynamic programming pass over the grid is not enough. This is a shortest path problem on a weighted graph whose nodes are the cells, so Dijkstra's algorithm applies.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ rows, cols ≤ 5; 1 ≤ costs[r][c] ≤ 9 - ◆
You start on the top-left cell and must reach the bottom-right cell, moving up, down, left or right (you may move in any of the four directions, also away from the goal) - ◆
Entering a cell costs its value; the value of the starting cell is also paid - ◆
Return the smallest total cost of a walk from the start cell to the destination cell
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Walk That Never Revisits a Cell
BruteExplore every walk that starts at the top-left cell and never steps on a cell twice (revisiting a cell can only add cost). Add up the cell values along the way and, whenever the bottom-right cell is reached, keep the smallest total. This depth-first search tries all self-avoiding walks, whose number grows explosively with the grid size.
O(4^(R·C)) walks (exponential)O(R·C)1class Solution {
2 private int best;
3
4 private void explore(int[][] costs, int r, int c, int total, boolean[][] onPath) {
5 int rows = costs.length, cols = costs[0].length;
6 total += costs[r][c];
7 if (r == rows - 1 && c == cols - 1) {
8 best = Math.min(best, total);
9 return;
10 }
11 int[] dr = {1, -1, 0, 0};
12 int[] dc = {0, 0, 1, -1};
13 onPath[r][c] = true;
14 for (int d = 0; d < 4; d++) {
15 int nr = r + dr[d], nc = c + dc[d];
16 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !onPath[nr][nc]) {
17 explore(costs, nr, nc, total, onPath);
18 }
19 }
20 onPath[r][c] = false;
21 }
22
23 public int cheapestWalk(int[][] costs) {
24 best = Integer.MAX_VALUE;
25 explore(costs, 0, 0, 0, new boolean[costs.length][costs[0].length]);
26 return best;
27 }
28}Optimal — Dijkstra’s Algorithm on the Grid
OptimalTreat each cell as a node; moving into a neighbour costs that neighbour's value. Keep the cheapest known cost for every cell (infinity except the start). Repeatedly take the unfinished cell with the smallest known cost — because all costs are positive, nothing can reach it more cheaply later — mark it finished, and improve its four neighbours with (its cost + neighbour's value). When the destination is finished, its cost is the answer. Scanning for the smallest cell takes O(R·C) per round; a heap makes it logarithmic.
O((R·C)²) (O(R·C log(R·C)) with a heap)O(R·C)1class Solution {
2 public int cheapestWalk(int[][] costs) {
3 int rows = costs.length, cols = costs[0].length;
4 int[] dr = {1, -1, 0, 0};
5 int[] dc = {0, 0, 1, -1};
6 int INF = Integer.MAX_VALUE;
7 int[][] dist = new int[rows][cols];
8 for (int[] row : dist) Arrays.fill(row, INF);
9 boolean[][] done = new boolean[rows][cols];
10 dist[0][0] = costs[0][0];
11 for (int round = 0; round < rows * cols; round++) {
12 int br = -1, bc = -1;
13 for (int r = 0; r < rows; r++) {
14 for (int c = 0; c < cols; c++) {
15 if (!done[r][c] && (br == -1 || dist[r][c] < dist[br][bc])) {
16 br = r;
17 bc = c;
18 }
19 }
20 }
21 if (dist[br][bc] == INF) break;
22 done[br][bc] = true;
23 for (int d = 0; d < 4; d++) {
24 int nr = br + dr[d], nc = bc + dc[d];
25 if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[br][bc] + costs[nr][nc] < dist[nr][nc]) {
26 dist[nr][nc] = dist[br][bc] + costs[nr][nc];
27 }
28 }
29 }
30 return dist[rows - 1][cols - 1];
31 }
32}