CSES - Grid Paths

Video Solution

By Vivian Han

See video code below.

Explanation

Adapted from /CPH.pdf#page=61

Basic Algorithm

The first version of the algorithm does not contain any optimizations. We simply use backtracking to generate all possible paths from the upper-left corner to the lower-right corner and count the number of such paths.

• Running time: $483$ seconds
• Number of recursive calls: $76$ billion

Optimization 1

If the path reaches the lower-right square before it has visited all other squares of the grid, it is clear that it will not be possible to complete the solution. Using this observation, we can terminate the search immediately if we reach the lower-right square too early.

• Running time: $119$ seconds
• Number of recursive calls: $20$ billion

Optimization 2

If the path touches a wall and can turn either left or right, the grid splits into two parts that contain unvisited squares. In this case, we cannot visit all squares anymore, so we can terminate the search.

• Running time: $1.8$ seconds
• Number of recursive calls: $221$ million

Optimization 3

The idea of Optimization 2 can be generalized: if the path cannot continue forward but can turn either left or right, the grid splits into two parts that both contain unvisited squares. It is clear that we cannot visit all squares anymore, so we can terminate the search.

• Running time: $0.6$ seconds
• Number of recursive calls: $69$ million

Now is a good moment to stop optimizing the algorithm and see what we have achieved. The running time of the original algorithm was $483$ seconds, and now after the optimizations, the running time is only $0.6$ seconds. Thus, the algorithm became nearly $1000$ times faster after the optimizations.

For C++ users, this will be enough pruning to make the program run in time under worst case conditions. However, for Java and Python users, this is still too slow (Java takes around $1.2$ seconds for the worst case). Thus, we will need to further optimize our search.

Optimization 4

If the path creates a dead end that is not the bottom left corner, either the path will fail to visit all squares (the path may stop at the dead end or pass over it, sealing a square off) or the path will end in the wrong location. Thus, we want to avoid creating dead ends. For example, if the square to the left of our current location is blocked on three sides (including our current location), then the next step must be to the left in order to avoid creating a dead end. After this optimization, the program runs in under $1$ second.

Implementation

Copy
#include <iostream>
using namespace std;

const int DIR_LEN = 4;
int dr[DIR_LEN] = {-1, 0, 1, 0};
int dc[DIR_LEN] = {0, 1, 0, -1};
const int PATH_LEN = 48;  // length of all possible paths
int p[PATH_LEN];
const int GRID_SIZE = 9;
// added border to all four sides so a 7x7 becomes a 9x9

Copy
import java.util.Scanner;

public class GridPaths {

	static boolean[][] onPath = new boolean[9][9];
	// added border to all four sides so a 7x7 becomes a 9x9
	static int[] dr = {-1, 0, 1, 0};  // transitions to up, right, down, left
	static int[] dc = {0, 1, 0, -1};  // for row and column, respectively
	static int[] p = new int[48];     // all possible paths have length 48