TSECJC06 - Editorial

Problem Link:

Practice

Contest

Author: tseccodecell

DIFFICULTY:

Medium

PRE-REQUISITES:

brute force, flood fill, grid traversal

PROBLEM:

You are given a grid of size N*M with some blocked cells

Find the longest path in the grid from one point to another or find that no path exists

QUICK EXPLANATION:

The constraints are low so a brute force algorithm would work

EXPLANATION:

The constraints are so low that we can try all paths and check the largest one by brute force.

One method is to make a funtion which finds the longest path from (x1, y1) to (x2, y2)

We mark the cell (x1, y1) as visited and continue to find longest path from it’s four adjacent cells.

Afterwards we unmark the cell (x1, y1) and return the maximum value found.

This algorithm will evaluate all paths starting from parent cell and return the maximum path length.

It is quite similar to flood fill algorithm.

Some limiting cases such as already visited node and outside boundary node would have to be taken care of.

Pseudo code for the function would be as follows:

int longest_path(x1, y1, x2, y2):

	if x1 == x2 and y1 == y2 :
		return 0

	if coordinates are out of boundary or (x1, y1) is already visited:
		return -100 

	visited[x1][y1] = true 
	
	// direction arrays useful for visiting neighbours
	dir_X[] = {1, 0, 0, -1} , dir_Y[] = {0, -1, 1, 0}

	int max_path_length = -100
	for i = 0 to 4 :
		max_path_length = max( max_path_length, 1 + longest_path(x1 + dir_X[i], y1 + dir_Y[i], x2, y2) )

	visited[x1][y1] = false

	return max_path_length

There definitely are other brute force solutions possible.

Some difficult test cases with answers :

Input:

3
5 5
3 3 2 2
##...
#..#.
.#...
#....
#.#..
3 5
2 3 0 1
.....
.....
.....
5 5
4 3 2 2
.###.
#.#..
.#...
###..
##..#

Output:

10
12
7

Time Complexity:

Time and Space complexity depends on the solution

It seems like time complexity is 4^{n*m} as we are doing recursion 4 times in one function call, but previous cell will always be visited, so actually it would be 3^{n*m} but some paths may end prematurely by going in a loop etc. so actual time complexity is much lower than this.

SOLUTION:

Author’s Solution

Tester’s Solution