Given an N*N matrix that all numbers are distinct in it, the function should find the maximum length path (starting from any cell) such that all the cells along the path are in increasing order with a difference of 1.
It can move in 4 directions from the given cell (i, j), It can move to (i-1, j) or (i, j-1) or (i+1, j) or (i, j+1) with the condition that the adjacent cells have a difference of 1.
I wrote the following code that works in all the cases that I have checked. I know that this is not optimal writing, with your permission, I would love to hear insights and ways to shorten the code. The program must be pure recursion without loops at all.
I'm not satisfied with the form and structure of my code because I went through the recursion step by step over all the options. I'm trying to write this in the form of backtracking with markings cells and stop conditions.
In the original question, the complexity of place, time, and the code are irrelevant.
At the moment, the discussion deals with the complexity of the code. I want to write it in a shorter and more elegant way while implementing backtracking.
public static int longestWorm(int[][] mat){
return longestWorm(mat, 0,0,0);
}
private static int longestWorm(int[][] mat,int i, int j, int max){
if (i == mat.length) return max;
if (j == mat[i].length-1)
return longestWorm(mat, i + 1, 0, max);
if (wormCount(mat,i,j,0) > max)
max = wormCount(mat,i,j,0);
return longestWorm(mat, i, j + 1, max);
}
private static int wormCount(int[][] mat, int i, int j,int count){
if(i < mat.length-1 && mat[i][j] == mat[i+1][j]+1)
return 1+ wormCount(mat, i+1, j, count+1);
if(j < mat[i].length-1 && mat[i][j] == mat[i][j+1]+1)
return 1+ wormCount(mat, i, j+1, count+1);
if(i > 0 && mat[i][j] == mat[i-1][j]+1)
return 1+ wormCount(mat, i-1, j, count+1);
if(j > 0 && mat[i][j] == mat[i][j-1]+1)
return 1+ wormCount(mat, i, j-1, count+1);
return count;
}