# Check for possible path in 2D matrix

Given a 2D array(m x n), check if there is any path from top left to bottom right. In the matrix, -1 is considered as blockage (can’t go through this cell) and 0 is considered path cell (can go through it).

Examples:

```Input : arr[][] = {{ 0, 0, 0, -1, 0},
{-1, 0, 0, -1, -1},
{ 0, 0, 0, -1, 0},
{-1, 0, 0,  0, 0},
{ 0, 0, -1,  0, 0}}
Output : Yes

Input : arr[][] = {{ 0, 0, 0, -1, 0},
{-1, 0, 0, -1, -1},
{ 0, 0, 0, -1, 0},
{-1, 0, -1,  0, 0},
{ 0, 0, -1,  0, 0}}
Output : No
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach :
A simple solution is to do BFS or DFS to find if there is a path.

A better solution is to mark all accessible nodes by changing their value to 1. First, change the value of the first top left element value to 1. Then get the next (current) value in the first row and compare to the previous value. Set this current value equal to the previous value only if it is reachable (not equal to -1). Similarly, do the same for column values, by comparing and setting the current with the previous column’s value if it is reachable.
Then start from the first-row & first column and take the values of previous row & the previous column. Find the max between them, and set the current index to that max. If the current index value is -1 then there’s no change.
In the end, if the final index at right bottom is 1 then return yes else return no.

## C++

 `// CPP program to find if there is path  ` `// from top left to right bottom ` `#include ` `using` `namespace` `std; ` ` `  `#define row 5 ` `#define col 5 ` ` `  `// to find the path from ` `// top left to bottom right ` `bool` `isPath(``int` `arr[row][col]) ` `{ ` `    ``// set arr[0][0] = 1 ` `    ``arr[0][0] = 1; ` ` `  `    ``// Mark reachable (from top left) nodes  ` `    ``// in first row and first column. ` `    ``for` `(``int` `i = 1; i < row; i++)  ` `        ``if` `(arr[0][i] != -1) ` `            ``arr[0][i] = arr[0][i - 1];    ` ` `  `    ``for` `(``int` `j = 1; j < col; j++)  ` `        ``if` `(arr[j][0] != -1) ` `            ``arr[j][0] = arr[j - 1][0];     ` ` `  `    ``// Mark reachable nodes in remaining ` `    ``// matrix. ` `    ``for` `(``int` `i = 1; i < row; i++)  ` `        ``for` `(``int` `j = 1; j < col; j++)  ` `          ``if` `(arr[i][j] != -1) ` `              ``arr[i][j] = max(arr[i][j - 1], ` `                            ``arr[i - 1][j]);        ` `     `  `    ``// return yes if right bottom  ` `    ``// index is 1 ` `    ``return` `(arr[row - 1][col - 1] == 1); ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``// Given array ` `    ``int` `arr[row][col] = { { 0, 0, 0, -1, 0 }, ` `                          ``{ -1, 0, 0, -1, -1 }, ` `                          ``{ 0, 0, 0, -1, 0 }, ` `                          ``{ -1, 0, -1, 0, -1 }, ` `                          ``{ 0, 0, -1, 0, 0 } }; ` ` `  `    ``// path from arr[0][0] to arr[row][col] ` `    ``if` `(isPath(arr)) ` `      ``cout << ``"Yes"``; ` `    ``else` `      ``cout << ``"No"``; ` ` `  `return` `0; ` `} `

## Java

 `// Java program to find if there is path ` `// from top left to right bottom ` `class` `GFG ` `{ ` `    ``// to find the path from ` `    ``// top left to bottom right ` `    ``static` `boolean` `isPath(``int` `arr[][]) ` `    ``{ ` `        ``// set arr[0][0] = 1 ` `        ``arr[``0``][``0``] = ``1``; ` ` `  `        ``// Mark reachable (from top left) nodes ` `        ``// in first row and first column. ` `        ``for` `(``int` `i = ``1``; i < ``5``; i++) ` `            ``if` `(arr[``0``][i] != -``1``) ` `                ``arr[``0``][i] = arr[``0``][i - ``1``]; ` `        ``for` `(``int` `j = ``1``; j < ``5``; j++) ` `            ``if` `(arr[j][``0``] != -``1``) ` `                ``arr[j][``0``] = arr[j - ``1``][``0``]; ` ` `  `        ``// Mark reachable nodes in ` `        ``//  remaining matrix. ` `        ``for` `(``int` `i = ``1``; i < ``5``; i++) ` `            ``for` `(``int` `j = ``1``; j < ``5``; j++) ` `                ``if` `(arr[i][j] != -``1``) ` `                    ``arr[i][j] = Math.max(arr[i][j - ``1``], ` `                                        ``arr[i - ``1``][j]); ` ` `  `        ``// return yes if right  ` `        ``// bottom index is 1 ` `        ``return` `(arr[``5` `- ``1``][``5` `- ``1``] == ``1``); ` `    ``} ` `      `  `    ``//Driver code  ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``// Given array ` `        ``int` `arr[][] = { { ``0``, ``0``, ``0``, -``1``, ``0` `}, ` `                        ``{ -``1``, ``0``, ``0``, -``1``, -``1` `}, ` `                        ``{ ``0``, ``0``, ``0``, -``1``, ``0` `}, ` `                        ``{ -``1``, ``0``, -``1``, ``0``, -``1` `}, ` `                        ``{ ``0``, ``0``, -``1``, ``0``, ``0` `} }; ` ` `  `        ``// path from arr[0][0]  ` `        ``// to arr[row][col] ` `        ``if` `(isPath(arr)) ` `            ``System.out.println(``"Yes"``); ` `        ``else` `            ``System.out.println(``"No"``); ` `    ``} ` `} ` `// This code is contributed  ` `// by prerna saini  `

/div>

## Python3

 `# Python3 program to find if there  ` `# is path from top left to right bottom  ` `row ``=` `5` `col ``=` `5` ` `  `# to find the path from  ` `# top left to bottom right  ` `def` `isPath(arr): ` `     `  `    ``# set arr[0][0] = 1 ` `    ``arr[``0``][``0``] ``=` `1` ` `  `    ``# Mark reachable (from top left)  ` `    ``# nodes in first row and first column.  ` `    ``for` `i ``in` `range``(``1``, row): ` `        ``if` `(arr[``0``][i] !``=` `-``1``): ` `            ``arr[``0``][i] ``=` `arr[``0``][i ``-` `1``] ` ` `  `    ``for` `j ``in` `range``(``1``, col): ` `        ``if` `(arr[j][``0``] !``=` `-``1``): ` `            ``arr[j][``0``] ``=` `arr[j ``-` `1``][``0``] ` `             `  `    ``# Mark reachable nodes in  ` `    ``# remaining matrix.  ` `    ``for` `i ``in` `range``(``1``, row): ` `        ``for` `j ``in` `range``(``1``, col): ` `            ``if` `(arr[i][j] !``=` `-``1``): ` `                ``arr[i][j] ``=` `max``(arr[i][j ``-` `1``],  ` `                                ``arr[i ``-` `1``][j]) ` `                                 `  `    ``# return yes if right  ` `    ``# bottom index is 1 ` `    ``return` `(arr[row ``-` `1``][col ``-` `1``] ``=``=` `1``) ` ` `  `# Driver Code  ` ` `  `# Given array  ` `arr ``=` `[[ ``0``, ``0``, ``0``, ``-``1``, ``0` `],  ` `       ``[``-``1``, ``0``, ``0``, ``-``1``, ``-``1``],  ` `       ``[ ``0``, ``0``, ``0``, ``-``1``, ``0` `],  ` `       ``[``-``1``, ``0``, ``-``1``, ``0``, ``-``1``],  ` `       ``[ ``0``, ``0``, ``-``1``, ``0``, ``0` `]]  ` ` `  `# path from arr[0][0] to arr[row][col]  ` `if` `(isPath(arr)): ` `    ``print``(``"Yes"``)  ` `else``: ` `    ``print``(``"No"``) ` ` `  `# This code is contributed  ` `# by sahilshelangia `

## C#

 `// C# program to find if there is path ` `// from top left to right bottom ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``// to find the path from ` `    ``// top left to bottom right ` `    ``static` `bool` `isPath(``int` `[,]arr) ` `    ``{ ` `        ``// set arr[0][0] = 1 ` `        ``arr[0, 0] = 1; ` ` `  `        ``// Mark reachable (from top left) nodes ` `        ``// in first row and first column. ` `        ``for` `(``int` `i = 1; i < 5; i++) ` `            ``if` `(arr[0, i] != -1) ` `                ``arr[0, i] = arr[0, i - 1]; ` `        ``for` `(``int` `j = 1; j < 5; j++) ` `            ``if` `(arr[j,0] != -1) ` `                ``arr[j,0] = arr[j - 1, 0]; ` ` `  `        ``// Mark reachable nodes in ` `        ``// remaining matrix. ` `        ``for` `(``int` `i = 1; i < 5; i++) ` `            ``for` `(``int` `j = 1; j < 5; j++) ` `                ``if` `(arr[i, j] != -1) ` `                    ``arr[i, j] = Math.Max(arr[i, j - 1], ` `                                        ``arr[i - 1, j]); ` ` `  `        ``// return yes if right  ` `        ``// bottom index is 1 ` `        ``return` `(arr[5 - 1, 5 - 1] == 1); ` `    ``} ` `     `  `    ``//Driver code  ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``// Given array ` `        ``int` `[,]arr = { { 0, 0, 0, -1, 0 }, ` `                        ``{ -1, 0, 0, -1, -1 }, ` `                        ``{ 0, 0, 0, -1, 0 }, ` `                        ``{ -1, 0, -1, 0, -1 }, ` `                        ``{ 0, 0, -1, 0, 0 } }; ` ` `  `        ``// path from arr[0][0]  ` `        ``// to arr[row][col] ` `        ``if` `(isPath(arr)) ` `            ``Console.WriteLine(``"Yes"``); ` `        ``else` `            ``Console.WriteLine(``"No"``); ` `    ``} ` `} ` ` `  `// This code is contributed  ` `// by vt_m `

## PHP

 ` `

Output:

```No
```

Time Complexity is O(n^2).