CareerCup

This is typically known as Percolation problem and widely used real life computing problems such electronics circuits,
Flow of fluid etc.
Now how do we correlate with what question is where ever there are 1's means its open site and keep moving till we find target through the 1's

Ways to solve this -
1) QuickUnion Algorithm

public class QuickUnionUF
{
private int[] id;
public QuickUnionUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
private int root(int i)
{
while (i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q)
{
return root(p) == root(q);
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
id[i] = j;
}

}


This will find the path in linear time.

More details can be found at - Search Quick Union Find

I assume that you can traverse the matrix in up, down, left and right direction.
Say that starting point A has coordinates A(r, c)
Check if any of neighboring points is equal 1
- up A(r-1, c)
- down A(r+1, c)
- left A(r, c -1)
- right A(r, c +1)
If any of this points is equal 1 invoke the method recursively with new coordinates eg new starting point is (r-1, c).
Repeat the process till you reach destination point or matrix's borders.
Simple code:

package interview;

public class FindPath {

    public static void main(String[] args) {

	int[][] m = { { 1, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 0, 0, 1, 1 } };
	System.out.println("Found path: " + findPath(0, 0, m.length - 1, m[0].length - 1, m));
    }

    private static boolean findPath(int startRow, int startCol, int endRow, int endCol, int[][] m) {

	if (startRow < 0 || startCol < 0 || endRow < 0 || endCol < 0 || startRow > m.length - 1
		|| startCol > m[0].length - 1 || endRow > m.length - 1 || endCol > m[0].length - 1) {

	    return false;
	}
	if (startRow == endRow && startCol == endCol) {
	    return true;
	}

	m[startRow][startCol] = -1;
	
	// go up
	boolean up = false;
	if (startRow - 1 >= 0 && m[startRow - 1][startCol] == 1) {
	    up = findPath(startRow - 1, startCol, endRow, endCol, m);
	}

	// go down
	boolean down = false;
	if (startRow + 1 <= m.length - 1 && m[startRow + 1][startCol] == 1) {
	    down = findPath(startRow + 1, startCol, endRow, endCol, m);
	}

	// go left
	boolean left = false;
	if (startCol - 1 >= 0 && m[startRow][startCol - 1] == 1) {
	    left = findPath(startRow, startCol - 1, endRow, endCol, m);
	}

	// go right
	boolean right = false;
	if (startCol + 1 <= m[0].length - 1 && m[startRow][startCol + 1] == 1) {
	    right = findPath(startRow, startCol + 1, endRow, endCol, m);
	}

	return up || down || right || left;
    }
}

You can also read about flood fill algorithm.