Tutorialspoint.dev

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



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 <iostream>
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 

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

<?php
// PHP 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
function isPath($arr)
{
    global $row, $col;
      
    $arr[0][0] = 1;
  
    // Mark reachable (from 
    // top left) nodes in 
    // first row and first column.
    for ($i = 1; $i < $row; $i++) 
        if ($arr[0][$i] != -1)
            $arr[0][$i] = $arr[0][$i - 1]; 
  
    for ($j = 1; $j < $col; $j++) 
        if ($arr[$j][0] != -1)
            $arr[$j][0] = $arr[$j - 1][0]; 
  
    // Mark reachable nodes 
    // in remaining matrix.
    for ($i = 1; $i < $row; $i++) 
        for ($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
  
// Given array
$arr = array(array(0, 0, 0, 1, 0),
             array(-1, 0, 0, -1, -1),
             array(0, 0, 0, -1, 0),
             array(-1, 0, -1, 0, -1),
             array(0, 0, -1, 0, 0));
  
// path from arr[0][0]
// to arr[row][col]
if (isPath($arr))
echo "Yes";
else
echo "No";
      
// This code is contributed by anuj_67.
?>


Output:

No

Time Complexity is O(n^2).



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter