 # TSECJC06 - Editorial

Practice

Contest

Author: tseccodecell

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

//