Back to Solutions

Grid Paths

Explanation

Here, we are given a 7 x 7 grid and an incomplete path that goes from the top left corner to the bottom left corner. We need to find the number of paths matching with the incomplete path.

The approach for this would be a backtracking algorithm where we will try to find all the possible paths and check if they match with the incomplete path. If they do, we will increment the count. But, this approach will take a lot of time and will not be efficient.

So, we'll apply 3 optimizations on it to make it efficient and finish under 1 second.

Sources: USACO Guide, CSES Book

Optimizations

1. Finish too early.

If we reach the bottom-left cell before all the other cells are visited then we can not consider that path and move on before checking all the cells.

2. Spliting the grid.

If we reach a cell after which we are able to move in only one axis and not the other axis, that means we will never be able to travel all the cells. So, we can stop there and move on to the next path.

Example:

Here, we won't be able to travel both sides of the grid. So, we can stop here and move on to the next path.

3. Dead Ends.

If we have a few cells to travel to and one of the cell is surrounded by 3 walls (including the current), then we must travel to that one, otherwise we won't be able to travel it later on.

Example:

Here, after reach (6, 1) we have 2 choices, either DOWN or RIGHT. If we choose DOWN, then the (7, 1) path will become a dead end, and returning after visiting that would be impossible. Thus we must choose RIGHT to avoid that.

Code

Unfortunately, I was not able to solve this problem in Python. So, I have provided the solution in Rust and C++.

use std::io;

fn main() {
    let mut incomplete_path = String::new();
    io::stdin().read_line(&mut incomplete_path).unwrap();
    let incomplete_path = incomplete_path.trim().chars().collect::<Vec<char>>();

    let mut count = 0;
    let mut explored = vec![vec![false; 9]; 9];

    for i in 1..=7 {
        explored[0][i] = true;
        explored[i][0] = true;
        explored[8][i] = true;
        explored[i][8] = true;
    }

    explore(1, 1, 0, &mut explored, &incomplete_path, &mut count);
    println!("{count}");
}

fn explore(
    x: usize,
    y: usize,
    index: usize,
    explored: &mut Vec<Vec<bool>>,
    path: &Vec<char>,
    count: &mut usize,
) {
    if x < 1 || y < 1 || x > 7 || y > 7 || explored[x][y] {
        return;
    }

    // optimization 1
    if x == 1 && y == 7 {
        if index == 48 {
            *count += 1;
        }
        return;
    }

    // optimization 2
    if (!explored[x - 1][y] && !explored[x + 1][y] && explored[x][y + 1] && explored[x][y - 1])
        || (explored[x - 1][y] && explored[x + 1][y] && !explored[x][y + 1] && !explored[x][y - 1])
    {
        return;
    }

    explored[x][y] = true;

    // optimization 3
    if path[index] == '?' {
        if y > 2
            && explored[x][y - 2]
            && (explored[x - 1][y - 1] || explored[x + 1][y - 1])
            && !explored[x][y - 1]
        {
            explore(x, y - 1, index + 1, explored, path, count);
            explored[x][y] = false;
            return;
        } else if y < 6
            && explored[x][y + 2]
            && (explored[x - 1][y + 1] || explored[x + 1][y + 1])
            && !explored[x][y + 1]
        {
            explore(x, y + 1, index + 1, explored, path, count);
            explored[x][y] = false;
            return;
        } else if x > 2
            && explored[x - 2][y]
            && (explored[x - 1][y - 1] || explored[x - 1][y + 1])
            && !explored[x - 1][y]
        {
            explore(x - 1, y, index + 1, explored, path, count);
            explored[x][y] = false;
            return;
        } else if x < 6
            && explored[x + 2][y]
            && (explored[x + 1][y - 1] || explored[x + 1][y + 1])
            && !explored[x + 1][y]
        {
            explore(x + 1, y, index + 1, explored, path, count);
            explored[x][y] = false;
            return;
        }
    }

    if path[index] == '?' || path[index] == 'L' {
        explore(x - 1, y, index + 1, explored, path, count);
    }
    if path[index] == '?' || path[index] == 'R' {
        explore(x + 1, y, index + 1, explored, path, count);
    }
    if path[index] == '?' || path[index] == 'U' {
        explore(x, y - 1, index + 1, explored, path, count);
    }
    if path[index] == '?' || path[index] == 'D' {
        explore(x, y + 1, index + 1, explored, path, count);
    }
    explored[x][y] = false;
}