# Find a Path in a Matrix (Java)

Given a 2d matrix, find a path from the top left corner to the bottom right corner. Assume there exists at least one path, and you only need to find one valid path. You can move up, right, down, left at any position.

For example, given

```[1, 0, 0, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 1, 0, 1]
[1, 0, 0, 0, 1]
[1, 0, 0, 0, 1]
```

A valid path is

```[1, 0, 0, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 1, 0, 1]
[0, 0, 0, 0, 1]
[0, 0, 0, 0, 1]
```

### Java Solution

```public int[][] findPath(int[][] matrix){
int m = matrix.length;

int[][] result = new int[m][m];

ArrayList<int[]> temp = new ArrayList<int[]>();
ArrayList<int[]> list = new ArrayList<int[]>();

dfs(matrix, 0, 0, temp, list);

for(int i=0; i<list.size(); i++){
result[list.get(i)[0]][list.get(i)[1]]=1;
//System.out.println(Arrays.toString(list.get(i)));
}

result[0][0]=1;

return result;
}

public void dfs(int[][] matrix, int i, int j,
ArrayList<int[]> temp,  ArrayList<int[]> list){

int m=matrix.length;

if(i==m-1 &amp;&amp; j==m-1){
list.clear();
return;
}

int[] dx = {-1, 0, 1, 0};
int[] dy = {0, 1, 0, -1};

for(int k=0; k<4; k++){
int x = i+dx[k];
int y = j+dy[k];

if(x>=0 &amp;&amp; y>=0 &amp;&amp; x<=m-1 &amp;&amp; y<=m-1 &amp;&amp; matrix[x][y]==1){