Problem Link:
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.