CareerCup

We can solve it by using a simple flood fill:

public final class Maze {
	private static boolean[][] m_visited;
	private static int[][] m_maze;
	
	public static boolean hasPath(int[][] maze, int startRow, int startCol, int destRow, int destCol){
		if(maze == null || maze.length == 0){
			return false;
		}
		m_visited = new boolean[maze.length][maze[0].length];
		m_maze = maze;
		visit(startRow,startCol);
		if(! m_visited[destRow][destCol]){
			return false;
		}
		return true;
	}

	
	private static void visit(int i, int j) {
		if(i < 0 || i >= m_visited.length || j < 0 || j >= m_visited[0].length || m_maze[i][j] == 1){
			return;
		}
		if(!m_visited[i][j]){
			m_visited[i][j] = true;
			visit(i-1, j); // Move left
			visit(i+1, j); // Move Right
			visit(i, j-1); //Move top
			visit(i, j+1); //Move bottom
		}
	}

	public static void main(String[] args) {
		int[][] maze = {{0, 0, 1, 1, 1},{0, 1, 0, 0, 0}, {1, 1, 1, 1, 1 },{0, 0, 0, 0, 1}};
		System.out.println(hasPath(maze, 0,0,1,2));
	}
}

Do a DFS. Make sure yuo don't get stuck in a cycle.

Nonrecursive DFS starting at the start position. Will operate in O(nm) complexity and O(nm) memory (no extra frame shifting too) where n and m are the dimensions of the binary array. This could potentially be sped up using something like A*, but that would take a bit more implementation.

public static boolean hasPath(int[][] arr, int[] start, int[] end){
    if(arr == null || start == null || end == null){
        throw new NullPointerException();
    }
    if(arr.length == 0 || arr[0].length == 0 || start.length !=2 || end.length != 2){
        throw new IllegalArgumentException();
    }

    boolean[][] alreadyChecked = new boolean[arr.length][arr[0].length];
    Stack<int[]> positionsToCheck = new Stack<int[]>();
    positionsToCheck.add(start);
    while(!positionsToCheck.isEmpty()){
        int[] pos = positionsToCheck.pop();
        if(Arrays.equals(pos, end)){
            return true;
        }
        if(pos[0] < 0 || pos[0] >= arr.length || pos[1] < 0 || pos[1] >= arr[0].length || arr[pos[0]][pos[1]] == 1 || alreadyChecked[pos[0]][pos[1]]){
            continue;
        }
        alreadyChecked[pos[0]][pos[1]] = true;
        positionsToCheck.add(new int[]{pos[0] - 1, pos[1]});
        positionsToCheck.add(new int[]{pos[0], pos[1] - 1});
        positionsToCheck.add(new int[]{pos[0] + 1, pos[1]});
        positionsToCheck.add(new int[]{pos[0], pos[1] + 1});
    }
    return false;
}

#include <iostream>
#include <cstring>

using namespace std;

const int DG = sizeof(unsigned int) * 8;

void resetBit(unsigned int &data, unsigned int bit) {
	if (bit < DG) {
		data &= ~(1 << (DG - 1 - bit));
	}
}

void setBit(unsigned int &data, unsigned int bit) {
	if (bit < DG) {
		data |= (1 << (DG - 1 - bit));
	}
}

unsigned int getBit(unsigned int data, unsigned int bit) {
	unsigned int res = 0;
	if (bit < DG) {
		res = ((data & (1 << (DG - 1 - bit))) == 0) ? 0 : 1;
	}

	return res;
}

void setIJ(unsigned int data[], int i, int j, const int cols) {
	int I = ((i * cols) + j) / DG;
	int J = ((i * cols) + j) % DG;

	setBit(data[I], J);
}


void resetIJ(unsigned int data[], int i, int j, const int cols) {
	int I = ((i * cols) + j) / DG;
	int J = ((i * cols) + j) % DG;

	resetBit(data[I], J);
}

int getIJ(unsigned int data[], int i, int j, const int cols) {
	int I = ((i * cols) + j) / DG;
	int J = ((i * cols) + j) % DG;

	return getBit(data[I], J);
}

bool findWay(unsigned int data[], int M, int N, int sx, int sy, int ex, int ey) {
	bool found = false;

	if ((sx == ex) && (sy == ey)) {
		found = true;
	} else {
		if (getIJ(data, sx, sy, N) == 0) {
			setIJ(data, sx, sy, N);

			if (sy - 1 >= 0) {	// left
				found = findWay(data, M, N, sx, sy - 1, ex, ey);
			}
			if (!found && (sx - 1 >= 0)) {	// top
				found =	findWay(data, M, N, sx - 1, sy, ex, ey);
			}
			if (!found && (sy + 1 < N)) {	// right
				found = findWay(data, M, N, sx, sy + 1, ex, ey);
			}
			if (!found && (sx + 1 < M)) {	//bottom
				found = findWay(data, M, N, sx + 1, sy, ex, ey);
			}
		} else {
			found = false;
		}
	}

	return found;
	}

int main() {
	int M;
	int N;
	unsigned int* data;
	int input = 0;

	cin >> M >> N;
	const int size = (M * N - 1) / DG + 1;

	data = new unsigned int[size];
	memset(data, 0, sizeof(unsigned int) * size);

	for (int i = 0; i < M; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> input;

			if (input != 0) {
				setIJ(data, i, j, N);
			}
		}
	}

	int sx, sy, ex, ey;
	cin >> sx >> sy >> ex >> ey;

	if (findWay(data, M, N, sx, sy, ex, ey)) {
		cout << "true" << endl;
	} else {
		cout << "false" << endl;
	}

	return 0;
}

In Ruby:

require 'thread'

def valid_move?(matrix=[], start_pt)
  start_pt[0] >= 0 && 
  start_pt[0] < matrix.length && 
  start_pt[1] >= 0 && 
  start_pt[1] < matrix.length
end

def mark_visited(visited, point)
  visited[point[0]..point[1]]=true
end

def visited?(visited, point)
  visited[point[0]..point[1]]
end

def move_left(start_pt)
  [start_pt[0],start_pt[1]-1]
end

def move_right(start_pt)
  [start_pt[0], start_pt[1]+1]
end

def move_up(start_pt)
  [start_pt[0]-1,start_pt[1]]
end

def move_down(start_pt)
  [start_pt[0]+1,start_pt[1]]
end

def exists_path_recursive?(matrix, start_pt, end_pt, visited,level)
  puts "Level: #{level}"
  puts "Start point: #{start_pt}"
  puts "End point: #{end_pt}"
 
  return true if start_pt == end_pt
  if !valid_move?(matrix, start_pt)
    puts "Invalid move: #{start_pt}"
    return false
  elsif visited?(visited,start_pt)
    puts "Already visited: #{start_pt}"
    return false 
  end
    
  puts "Mark visited: #{start_pt}"
  mark_visited(visited,start_pt)
  puts "Visited: #{visited}"
  
  return exists_path?(matrix, move_left(start_pt),end_pt,visited,level+1) || 
  exists_path?(matrix, move_right(start_pt),end_pt,visited,level+1) ||
  exists_path?(matrix, move_up(start_pt),end_pt,visited,level+1)  ||
  exists_path?(matrix, move_down(start_pt),end_pt,visited,level+1)
end

def exists_path_nonrecursive?(matrix, start_pt,end_pt, visited)
  queue = Queue.new
  queue << start_pt
  puts "Queue size: #{queue.length}"
  puts
  
  while !queue.empty?
    point = queue.pop
    puts "Queue size after pop: #{queue.length}"
    
    if visited?(visited,point)
      puts "Already visited #{point}"
      puts
      next
    end
    
    mark_visited(visited,point)
    puts "Visited: #{visited}"
    
    return true if point == end_pt
    
    if valid_move?(matrix,move_left(point))
      puts "Move left: #{move_left(point)}"
      queue << move_left(point)
      puts "Queue size after push: #{queue.length}"
    end
    
    if valid_move?(matrix,move_right(point))
      puts "Move right: #{move_right(point)}"
      queue << move_right(point)
      puts "Queue size after push: #{queue.length}"
    end
    
    if valid_move?(matrix,move_up(point))
      puts "Move up: #{move_up(point)}"
      queue << move_up(point)
      puts "Queue size after push: #{queue.length}"
    end
    
    if valid_move?(matrix,move_down(point))
      puts "Move down: #{move_down(point)}"
      queue << move_down(point)
      puts "Queue size after push: #{queue.length}"
    end
    
    puts
  end
  
  return false
end

matrix=[
  [0,0,1,0,1],
  [0,0,0,0,0],
  [0,1,1,1,1],
  [0,1,1,0,0],
  [0,0,1,0,0]
]

start_pt=[4,1]
end_pt=[0,3]

visited={}

puts "Exists path? #{exists_path_nonrecursive?(matrix,start_pt,end_pt,visited)}"

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package Dummy;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

/**
 *
 * @author
 */
public class Dummy02 {
    
    static Stack<int[]> accesspoints=new Stack<int[]>();
    
    public static boolean findPath(int[][] points, int[] startpt, int[] endpt)
    {
        
        int[][] pointsvisited=new int[points.length][points[0].length];
        
        accesspoints.add(startpt);
        visitpoint(points,pointsvisited,startpt);
        
        for(int[] coord:accesspoints)
        {
            if((coord[0]==endpt[0])&&(coord[1]==endpt[1]))
                return true;
        }
        
        return false;
        
    }
    
    public static void visitpoint(int[][] points, int[][] pointsvisited , int [] currentpoint)
    {
        if(currentpoint[0]<0||currentpoint[0]>=points.length||currentpoint[1]<0||currentpoint[1]>=points[0].length||
                pointsvisited[currentpoint[0]][currentpoint[1]]==1||points[currentpoint[0]][currentpoint[1]]==1)
        {
            return ;
        }
        
        pointsvisited[currentpoint[0]][currentpoint[1]]=1;
        accesspoints.add(currentpoint);
        visitpoint(points,pointsvisited,new int[]{currentpoint[0]+1,currentpoint[1]});
        visitpoint(points,pointsvisited,new int[]{currentpoint[0]-1,currentpoint[1]});
        visitpoint(points,pointsvisited,new int[]{currentpoint[0],currentpoint[1]+1});
        visitpoint(points,pointsvisited,new int[]{currentpoint[0],currentpoint[1]-1});
        
    }
    
    
    
    
   static BufferedReader br;
   static StringTokenizer st;
    
    public static void main(String args[]) throws IOException
    {
        br=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the dimensions of the value matrix");
        int length=nextInt();
        int breadth=nextInt();
        int[][] points=new int[length][breadth];
        System.out.println("Enter the matrix");
        for(int i=0;i<length;i++)
        {
            for(int j=0;j<breadth;j++)
            {
                points[i][j]=nextInt();
            }
        }
        int[] startpt=new int[2];
        int[] endpt=new int[2];
        
        System.out.println("Enter the starting point");
        for(int i=0;i<2;i++)
        {
            startpt[i]=nextInt();
        }    
        System.out.println("Enter the coordinates of end point");
        for(int i=0;i<2;i++)
        {
            endpt[i]=nextInt();
        }    
            
       boolean value=findPath(points,startpt,endpt);
        
       if(value)
           System.out.println("There exist a path");
       else
            System.out.println("There exist no path");
        
        
        
    }
    
    
    public static int nextInt() throws IOException
    {
        return Integer.parseInt(nextToken());
    }
    
    public static String nextToken() throws IOException
    {
        while(st==null||!st.hasMoreTokens())
        {
            String line=br.readLine();
            if(line==null)
                return line;
            
            st=new StringTokenizer(line.replaceAll("", " "));
        }
       return st.nextToken();
    }
    
}

in input just flip for x and y

1. Create a List of separate graphs of each connected component of 1s
2. given 2 points check if they're in the same graph if so, path is possible, if not, no path possible.

Since we're not looking at the shortest path, I would try greedy best first search algorithm, as it generally finds the solution faster than regular BFS or DFS.
The calculated distance between two nodes would be the sum of the horizontal distance and the vertical distance, since we can't move in diagonals.

As above said,this can be done using dfs as well as bfs.Here's I implemented the same

#include <bits/stdc++.h>
using namespace std;
#define maxx 100
#define pb push_back
#define pii pair<int,int>
vector<pii>vpii[maxx];
#define inf 0x7fffffff
int X[]={+1,-1,0,0};//possible movements
int Y[]={0,0,+1,-1};
vector<int>v[maxx];
bool vis[maxx][maxx];
int a[4][5];
struct data
{
  int x,y;
  void set(int i,int j)
  {
      x=i;
      y=j;
  }
};
void dfs(data s)
{
    vis[s.x][s.y]=true;
    for(int i=0;i<4;i++)
    {
        data t;
        int t1=s.x+X[i];
        int t2=s.y+Y[i];
        if(vis[t1][t2]==false && t1<4 && t1>=0 && t2>=0 && t2<5&& a[t1][t2]==0)
        {
            vis[t1][t2]=true;
            t.set(t1,t2);
            dfs(t);
        }
    }
}
int main() {
    memset(vis,false,sizeof vis);
    for(int i=0;i<4;++i)
        for(int j=0;j<5;++j)
          cin>>a[i][j];
    data start,endd;
    cin>>start.x>>start.y;
    cin>>endd.x>>endd.y;
    dfs(start);
    if(vis[endd.x][endd.y])
        cout<<"true";
    else
        cout<<"false";
	return 0;
}

package com.pc.careerCup;

public class MetricPath{
	
	public static void main(String args[]){
		int[][] a={{0,0,1,0,1},
			       {0,0,0,0,0},
				   {0,1,1,1,1},
				   {0,1,1,0,0}};
		int[][] visited= a; 
		System.out.println("Result : " + isPath(a,  0, 3,3, 0, visited));
	}
	
	private static boolean isPath(int[][] a, int x, int y, int endX, int endY, int[][] visited){
		System.out.print("{" + x + "," + y + "} ->");

		if(x == endX && y==endY){
			return true;
		}
		
		boolean result=false;
		visited[x][y]=1;
		
		//Move up
		if(x-1>=0 && (visited[x-1][y]!=1)){
			
			result=isPath(a, x-1, y, endX, endY, visited);
		}
		
		//Move down
		if((!result) && (x+1 < a.length) && (visited[x+1][y]!=1)){
			result=isPath(a, x+1, y, endX, endY, visited);
		}
		
		//Move left
		if((!result) && (y-1 >=0 )&& (visited[x][y-1]!=1)){
			result=isPath(a, x, y-1,endX, endY, visited);
		}
		
		//Move right
		if((!result) && (y + 1 <a[0].length) && (visited[x][y+1]!=1)){
			result=isPath(a, x, y+1,endX, endY, visited );
		}
	return result;
	}
}

Why you guys have to put so many code for a DFS? DFS recursive should only be as simple as this:

class Solution:
	matrix=[]
	xlimit=0
	ylimit=0
	endpoint=[]
	stack=[]
	result=0
	
	def findpath(self,matrix,startpoint,endpoint):
		self.matrix = matrix
		self.xlimit=len(matrix)
		self.ylimit=len(matrix[0])
		self.endpoint=endpoint
		self.stack.append([startpoint[0],startpoint[1]])
		self.DFS(startpoint[0],startpoint[1])
		
		if self.result <> 0:
			return True
		return False
		
	
	def DFS(self,x,y):
		if x==self.endpoint[0] and y==self.endpoint[1]:
			print 'we reached it finally this is the path:', self.stack
			self.result+=1
			return
		if x+1<self.xlimit and self.matrix[x+1][y]==0 and [x+1,y] not in self.stack:
			self.stack.append([x+1,y])
			self.DFS(x+1,y)
			self.stack.pop()
		if x-1>=0 and self.matrix[x-1][y]==0 and [x-1,y] not in self.stack:
			self.stack.append([x-1,y])
			self.DFS(x-1,y)
			self.stack.pop()
		if y+1<self.ylimit and self.matrix[x][y+1]==0 and [x,y+1] not in self.stack: 
			self.stack.append([x,y+1])
			self.DFS(x,y+1)
			self.stack.pop()
		if y-1>=0 and self.matrix[x][y-1]==0 and [x,y-1] not in self.stack:
			self.stack.append([x,y-1])
			self.DFS(x,y-1)
			self.stack.pop()

Why you guys have to write this many code. A DFS recursive should be as simple as this

class Solution:
	matrix=[]
	xlimit=0
	ylimit=0
	endpoint=[]
	stack=[]
	result=0
	
	def findpath(self,matrix,startpoint,endpoint):
		self.matrix = matrix
		self.xlimit=len(matrix)
		self.ylimit=len(matrix[0])
		self.endpoint=endpoint
		self.stack.append([startpoint[0],startpoint[1]])
		self.DFS(startpoint[0],startpoint[1])
		
		if self.result <> 0:
			return True
		return False
		
	
	def DFS(self,x,y):
		if x==self.endpoint[0] and y==self.endpoint[1]:
			print 'we reached it finally this is the path:', self.stack
			self.result+=1
			return
		if x+1<self.xlimit and self.matrix[x+1][y]==0 and [x+1,y] not in self.stack:
			self.stack.append([x+1,y])
			self.DFS(x+1,y)
			self.stack.pop()
		if x-1>=0 and self.matrix[x-1][y]==0 and [x-1,y] not in self.stack:
			self.stack.append([x-1,y])
			self.DFS(x-1,y)
			self.stack.pop()
		if y+1<self.ylimit and self.matrix[x][y+1]==0 and [x,y+1] not in self.stack: 
			self.stack.append([x,y+1])
			self.DFS(x,y+1)
			self.stack.pop()
		if y-1>=0 and self.matrix[x][y-1]==0 and [x,y-1] not in self.stack:
			self.stack.append([x,y-1])
			self.DFS(x,y-1)
			self.stack.pop()

Simple DFS approch would work.

1. Add start Node to Stack
2. Continue 3. till stack is not empty or goal node reached
3. Explore top, bottom, left, right. Add to stack

class Solution:
matrix = []
xlimit = 0
ylimit = 0
result = 1

def findpath(self, matrix, startpoint):
self.matrix = matrix
self.xlimit = len(matrix)
self.ylimit = len(matrix[0])
nsteps = self.DFS(startpoint[0],startpoint[1])
if nsteps == 0:
return -1
return nsteps

def DFS(self,x,y):
if x+1 < self.xlimit:
if self.matrix[x+1][y] == 1:
self.result += 1
return self.DFS(x+1, y)
elif self.matrix[x+1][y]==9:
return self.result
if y+1 < self.ylimit:
if self.matrix[x][y+1] == 1:
self.result += 1
return self.DFS(x, y+1)
elif self.matrix[x][y+1]==9:
return self.result
if x-1 >= 0:
if self.matrix[x-1][y] == 1:
self.result += 1
return self.DFS(x-1, y)
elif self.matrix[x-1][y]==9:
return self.result
if y-1 >= 0:
if self.matrix[x][y-1] == 1:
self.result += 1
return self.DFS(x, y-1)
elif self.matrix[x][y-1]==9:
return self.result

a = Solution()
print(a.findpath([[1,0,0],[1,0,0],[1,9,1]], (0, 0)))
b = Solution()
print(b.findpath([[1,1,1,1],[0,1,1,1],[0,1,0,1],[1,1,9,1],[0,0,1,1]], (0,0)))

class Solution:
  matrix = []
  xlimit = 0
  ylimit = 0
  result = 1
  
  def findpath(self, matrix, startpoint):
    self.matrix = matrix
    self.xlimit = len(matrix)
    self.ylimit = len(matrix[0])
    nsteps = self.DFS(startpoint[0],startpoint[1])
    if nsteps == 0:
      return -1
    return nsteps
    
  def DFS(self,x,y):
    if x+1 < self.xlimit:
      if self.matrix[x+1][y] == 1:
        self.result += 1
        return self.DFS(x+1, y)
      elif self.matrix[x+1][y]==9:
        return self.result
    if y+1 < self.ylimit:
      if self.matrix[x][y+1] == 1: 
        self.result += 1
        return self.DFS(x, y+1)
      elif self.matrix[x][y+1]==9:
        return self.result
    if x-1 >= 0:
      if self.matrix[x-1][y] == 1:
        self.result += 1
        return self.DFS(x-1, y)
      elif self.matrix[x-1][y]==9:
        return self.result
    if y-1 >= 0:
      if self.matrix[x][y-1] == 1:
        self.result += 1
        return self.DFS(x, y-1)
      elif self.matrix[x][y-1]==9:
        return self.result

a = Solution()
print(a.findpath([[1,0,0],[1,0,0],[1,9,1]], (0, 0)))
b = Solution()
print(b.findpath([[1,1,1,1],[0,1,1,1],[0,1,0,1],[1,1,9,1],[0,0,1,1]], (0,0)))

Here is the solution to reach a destination 9 in a matrix

class Solution:
  matrix = []
  xlimit = 0
  ylimit = 0
  result = 1
  
  def findpath(self, matrix, startpoint):
    self.matrix = matrix
    self.xlimit = len(matrix)
    self.ylimit = len(matrix[0])
    nsteps = self.DFS(startpoint[0],startpoint[1])
    if nsteps == 0:
      return -1
    return nsteps
    
  def DFS(self,x,y):
    if x+1 < self.xlimit:
      if self.matrix[x+1][y] == 1:
        self.result += 1
        return self.DFS(x+1, y)
      elif self.matrix[x+1][y]==9:
        return self.result
    if y+1 < self.ylimit:
      if self.matrix[x][y+1] == 1: 
        self.result += 1
        return self.DFS(x, y+1)
      elif self.matrix[x][y+1]==9:
        return self.result
    if x-1 >= 0:
      if self.matrix[x-1][y] == 1:
        self.result += 1
        return self.DFS(x-1, y)
      elif self.matrix[x-1][y]==9:
        return self.result
    if y-1 >= 0:
      if self.matrix[x][y-1] == 1:
        self.result += 1
        return self.DFS(x, y-1)
      elif self.matrix[x][y-1]==9:
        return self.result

a = Solution()
print(a.findpath([[1,0,0],[1,0,0],[1,9,1]], (0, 0)))
b = Solution()
print(b.findpath([[1,1,1,1],[0,1,1,1],[0,1,0,1],[1,1,9,1],[0,0,1,1]], (0,0)))