I have an m*n matrix where every element is unique. From a given starting point I have to move to the smallest point in a relative direction (e.g. up, down, left, right) and then have to repeat the process again. When all other surrounding points have a value that is greater than the existing one I have to stop and print the position from start. Suppose I have a 5x5 matrix:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
and starting point is (2,2) then the output will be 13,8,3,2,1.
I have solved this problem my way, but the problem is its complexity. I do not think my solution is efficient. Can anyone suggest to me a better solution?
N.B: Except scanner pkg, I am not allowed to import any other pkg. Here is my code:
import java.util.Arrays;
import java.util.Scanner;
public class DirectionArray {
public static void main(String [] args) {
Scanner in = new Scanner(System.in);
int row = in.nextInt();
int col = in.nextInt();
int[][] ara = new int[row][col];
int[] ara2 = new int[4];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
ara[i][j] = in.nextInt();
}
}
System.out.println("Give starting point(x) ");
int x= in.nextInt();
System.out.println("Give starting point(y) ");
int y= in.nextInt();
int sx=x;
int sy =y;
int [] fx={+1,-1,0,0};
int [] fy={0,0,+1,-1};
int p=0;
int l=0;
int v=0;
int r=0;
int [] result=new int[row*col] ;
int min=ara[x][y];
boolean swap=true;
for(int i=0;i<(row*col)-1;i++) {
for (int k = 0; k < 4; k++) {
int nx = x + fx[k];
int ny = y + fy[k];
if (nx >= 0 && nx < row && ny >= 0 && ny < col) {
if (min > ara[nx][ny]) {
ara2[p] = ara[nx][ny];
p++;
// x = nx;
//y = ny;
}
}
}
p=0;
while(swap) {
swap=false;
r++;
for (int q = 0; q < ara2.length-r; q++) {
if(ara2[q]>ara2[q+1]){
int temp = ara2[q];
ara2[q]=ara2[q+1];
ara2[q+1]=temp;
swap=true;
}
}
}
// Arrays.sort(ara2);
for(int j=0;j<ara2.length;j++) {
if(ara2[j]!=0)
{
v=ara2[j];
result[l]=v;
l++;
break;
}
}
// System.out.println(v);
min=v;
for(int o=0;o<ara2.length;o++) {
ara2[o]=0;
}
for(int m=0;m<row;m++){
for(int n=0;n<col;n++){
if(ara[m][n]==v) {
x = m;
y = n;
}
}
}
}
System.out.print(ara[sx][sy]+" ");
for(int i=0;i<result.length;i++) {
if(result[i]!=0) {
System.out.print(result[i] + " ");
}
if(result[i]==0) {
break;
}
}
}
}