Monday, August 17, 2015

Matrix - Moving from one cell to another

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