Problem
Given an nxm matrix, filled with either 1 or 0. If a cell has value 1, then you cannot move into it. If it has 0, then you can move into it. You're given a starting position (sx, sy), where sx indicates a row on the matrix, and sy a column on the matrix. Check if a move is possible from (sx, sy) to another position (ex, ey). Return true if possible, otherwise return false.
Solution
public class MatrixMove {
boolean valid(int[][]m, int x, int y)
{
if(x < m.length && y< m[0].length && x >= 0 && y>= 0 ) return true;
return false;
}
boolean move(int[][] m, int sx, int sy, int ex, int ey)
{
if(!valid(m,sx, sy) || !valid(m,ex, ey)) return false;
if(m[sx][sy] == 1 || m[ex][ey]==1) return false;
if(sx == ex && sy == ey) return true;
m[sx][sy] = 1;
return move(m,sx-1,sy,ex,ey) || move(m,sx+1,sy,ex,ey)
|| move(m, sx, sy-1, ex,ey) || move(m,sx,sy+1, ex, ey);
}
public static void main(String[] args) {
int[][] m = {{0,0,1,0,1}, {0,0,0,0,0}, {0,1,1,1,1}, {0,0,0,0,0}, {0,1,1,1,0}};
int sx=1, sy =1, ex=4, ey=4;
MatrixMove ob = new MatrixMove();
System.out.println(ob.move(m, sx, sy, ex, ey));
}
}
No comments:
Post a Comment