Print the indices for every row of a grid from which escaping from the grid is possible

Last Updated : 17 May, 2021

Given a binary 2D array arr[] of dimension M * N representing a grid where ‘0‘ represents that there is a wall on the main diagonal of the cell and ‘1‘ represents that there is a wall on cross diagonal of the cell. The task is for every i^th row is to print the index of the row from which one can escape the grid, given that one cannot escape from the top or bottom of the grid.

Examples:

Input: arr[][] = {{1, 1, 0, 1}, {1, 1, 0, 0}, {1, 0, 0, 0}, {1, 1, 0, 1}, {0, 1, 0, 1}}
Output: -1 -1 2 3 -1
Explanation:

No escape path exists from the rows 0, 1 or 4.
If a person enters the grid from the 2^nd row, then he will come out of the grid from the cell (2, 3) following the path shown in the diagram above.
If a person enters the grid from the 3^rd row, then he will come out of the grid from the cell (3, 3) following the path shown in the diagram above.

Input: arr[][] = {{1, 1, 0}, {0, 1, 0}, {0, 1, 0}, {0, 1, 0}}
Output: -1 2 3 -1

Approach: The given problem can be solved based on the following observations:

From the above image, it can be observed that for a given orientation of wall depending upon the direction in which a person enters a cell there is only one choice for exiting that cell.
Therefore, for each row, the idea is to iterate in the given direction keeping track of the direction in which a person enters the cell.

Follow the steps below to solve the problem:

Iterate over the range [0, M – 1] using a variable row and perform the following operations:
- Initialize two variables say i and j to store the row index and column index of the cell in which the person is currently in.
- Assign row to i and 0 to j.
- Initialize a variable, say dir, to store the direction in which a person enters a cell.
- Iterate until j is not at least N and perform the following operations:
  - If arr[i][j] is 1 then check the following conditions:
    - If dir is equal to ‘L‘ then decrement i by 1 and assign ‘D‘ to dir.
    - Otherwise, if dir is equal to ‘U‘ then decrement j by 1 and assign ‘R‘ to dir.
    - Otherwise, if dir is equal to ‘R‘ then increment i by 1 and assign ‘U‘ to dir.
    - Otherwise, increment j by 1 and assign ‘L‘ to dir.
  - Otherwise, if arr[i][j] is 0 then check the following conditions:
    - If dir is equal to ‘L‘ then increment i by 1 and assign ‘U‘ to dir.
    - Otherwise, if dir is equal to ‘U‘ then increment j by 1 and assign ‘L‘ to dir.
    - Otherwise, if dir is equal to ‘R‘ then decrement i by 1 and assign ‘D‘ to dir.
    - Otherwise, decrement j by 1 and assign ‘R‘ to dir.
  - Otherwise, if i or j is 0 or i is equal to M or j is equal to N then break.
- If j is equal to N then print the value i.
- Otherwise, print -1.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the row index for
// every row of a matrix from which one
// can exit the grid after entering from left
void findPath(vector<vector<int> >& arr,
              int M, int N)
{
    // Iterate over the range [0, M-1]
    for (int row = 0; row < M; row++) {
 
        // Stores the direction from
        // which a person enters a cell
        char dir = 'L';
 
        // Row index from which
        // one enters the grid
        int i = row;
 
        // Column index from which
        // one enters the grid
        int j = 0;
 
        // Iterate until j is atleast N-1
        while (j < N) {
 
            // If Mat[i][j] is equal to 1
            if (arr[i][j] == 1) {
 
                // If entry is from left cell
                if (dir == 'L') {
 
                    // Decrement i by 1
                    i--;
 
                    // Assign 'D' to dir
                    dir = 'D';
                }
 
                // If entry is from upper cell
                else if (dir == 'U') {
                    // Decrement j by 1
                    j--;
                    // Assign 'R' to dir
                    dir = 'R';
                }
                // If entry is from right cell
                else if (dir == 'R') {
 
                    // Increment i by 1
                    i++;
 
                    // Assign 'U' to dir
                    dir = 'U';
                }
 
                // If entry is from bottom cell
                else if (dir == 'D') {
 
                    // Increment j by 1
                    j++;
 
                    // Assign 'L' to dir
                    dir = 'L';
                }
            }
 
            // Otherwise,
            else {
                // If entry is from left cell
                if (dir == 'L') {
 
                    // Increment i by 1
                    i++;
 
                    // Assign 'U' to dir
                    dir = 'U';
                }
 
                // If entry is from upper cell
                else if (dir == 'U') {
 
                    // Increment j by 1
                    j++;
 
                    // Assign 'L' to dir
                    dir = 'L';
                }
 
                // If entry is from right cell
                else if (dir == 'R') {
 
                    // Decrement i by 1
                    i--;
 
                    // Assign 'D' to dir
                    dir = 'D';
                }
                // If entry is from lower cell
                else if (dir == 'D') {
 
                    // Decrement j by 1
                    j--;
 
                    // Assign 'R' to dir
                    dir = 'R';
                }
            }
 
            // If i or j is less than 0 or i is
            // equal to M or j is equal to N
            if (i < 0 || i == M || j < 0 || j == N)
                break;
        }
 
        // If j is equal to N
        if (j == N)
            cout << i << " ";
 
        // Otherwise
        else
            cout << -1 << " ";
    }
}
// Driver Code
int main()
{
    // Input
    vector<vector<int> > arr = { { 1, 1, 0, 1 },
                                 { 1, 1, 0, 0 },
                                 { 1, 0, 0, 0 },
                                 { 1, 1, 0, 1 },
                                 { 0, 1, 0, 1 } };
    int M = arr.size();
    int N = arr[0].size();
 
    // Function call
    findPath(arr, M, N);
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the row index for
// every row of a matrix from which one
// can exit the grid after entering from left
static void findPath(int [][]arr,
                     int M, int N)
{
     
    // Iterate over the range [0, M-1]
    for(int row = 0; row < M; row++)
    {
         
        // Stores the direction from
        // which a person enters a cell
        char dir = 'L';
 
        // Row index from which
        // one enters the grid
        int i = row;
 
        // Column index from which
        // one enters the grid
        int j = 0;
 
        // Iterate until j is atleast N-1
        while (j < N) 
        {
             
            // If Mat[i][j] is equal to 1
            if (arr[i][j] == 1) 
            {
 
                // If entry is from left cell
                if (dir == 'L')
                {
                     
                    // Decrement i by 1
                    i--;
 
                    // Assign 'D' to dir
                    dir = 'D';
                }
 
                // If entry is from upper cell
                else if (dir == 'U') 
                {
                     
                    // Decrement j by 1
                    j--;
                     
                    // Assign 'R' to dir
                    dir = 'R';
                }
                 
                // If entry is from right cell
                else if (dir == 'R') 
                {
                     
                    // Increment i by 1
                    i++;
 
                    // Assign 'U' to dir
                    dir = 'U';
                }
 
                // If entry is from bottom cell
                else if (dir == 'D') 
                {
                     
                    // Increment j by 1
                    j++;
 
                    // Assign 'L' to dir
                    dir = 'L';
                }
            }
 
            // Otherwise,
            else
            {
                 
                // If entry is from left cell
                if (dir == 'L')
                {
                     
                    // Increment i by 1
                    i++;
 
                    // Assign 'U' to dir
                    dir = 'U';
                }
 
                // If entry is from upper cell
                else if (dir == 'U') 
                {
                     
                    // Increment j by 1
                    j++;
 
                    // Assign 'L' to dir
                    dir = 'L';
                }
 
                // If entry is from right cell
                else if (dir == 'R')
                {
                     
                    // Decrement i by 1
                    i--;
 
                    // Assign 'D' to dir
                    dir = 'D';
                }
                 
                // If entry is from lower cell
                else if (dir == 'D') 
                {
                     
                    // Decrement j by 1
                    j--;
 
                    // Assign 'R' to dir
                    dir = 'R';
                }
            }
 
            // If i or j is less than 0 or i is
            // equal to M or j is equal to N
            if (i < 0 || i == M || j < 0 || j == N)
                break;
        }
 
        // If j is equal to N
        if (j == N)
            System.out.print(i + " ");
 
        // Otherwise
        else
            System.out.print(-1 + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Input
    int [][]arr = { { 1, 1, 0, 1 },
                    { 1, 1, 0, 0 },
                    { 1, 0, 0, 0 },
                    { 1, 1, 0, 1 },
                    { 0, 1, 0, 1 } };
    int M = arr.length;
    int N = arr[0].length;
 
    // Function call
    findPath(arr, M, N);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program
# for the above approach
 
# Function to find the row index for
# every row of a matrix from which one
# can exit the grid after entering from left
def findPath(arr, M,  N) :
     
    # Iterate over the range [0, M-1]
    for row in range(M):
  
        # Stores the direction from
        # which a person enters a cell
        dir = 'L'
  
        # Row index from which
        # one enters the grid
        i = row
  
        # Column index from which
        # one enters the grid
        j = 0
  
        # Iterate until j is atleast N-1
        while (j < N) :
  
            # If Mat[i][j] is equal to 1
            if (arr[i][j] == 1) :
  
                # If entry is from left cell
                if (dir == 'L') :
  
                    # Decrement i by 1
                    i -= 1
  
                    # Assign 'D' to dir
                    dir = 'D'
                 
  
                # If entry is from upper cell
                elif (dir == 'U') :
                    # Decrement j by 1
                    j -= 1
                    # Assign 'R' to dir
                    dir = 'R'
                 
                # If entry is from right cell
                elif (dir == 'R') :
  
                    # Increment i by 1
                    i += 1
  
                    # Assign 'U' to dir
                    dir = 'U'
                 
  
                # If entry is from bottom cell
                elif (dir == 'D') :
  
                    # Increment j by 1
                    j += 1
  
                    # Assign 'L' to dir
                    dir = 'L'
                 
             
  
            # Otherwise,
            else :
                # If entry is from left cell
                if (dir == 'L') :
  
                    # Increment i by 1
                    i += 1
  
                    # Assign 'U' to dir
                    dir = 'U'
                 
  
                # If entry is from upper cell
                elif (dir == 'U') :
  
                    # Increment j by 1
                    j += 1
  
                    # Assign 'L' to dir
                    dir = 'L'
                 
  
                # If entry is from right cell
                elif (dir == 'R') :
  
                    # Decrement i by 1
                    i -= 1
  
                    # Assign 'D' to dir
                    dir = 'D'
                 
                # If entry is from lower cell
                elif (dir == 'D') :
  
                    # Decrement j by 1
                    j -= 1
  
                    # Assign 'R' to dir
                    dir = 'R'
                 
             
  
            # If i or j is less than 0 or i is
            # equal to M or j is equal to N
            if (i < 0 or i == M or j < 0 or j == N):
                break
         
  
        # If j is equal to N
        if (j == N) :
            print(i, end = " ")
  
        # Otherwise
        else :
            print(-1, end = " ")
     
 
# Driver Code
 
arr = [[ 1, 1, 0, 1 ],
    [ 1, 1, 0, 0 ],
    [ 1, 0, 0, 0 ],
    [ 1, 1, 0, 1 ],
    [ 0, 1, 0, 1 ]] 
 
M = len(arr)
N = len(arr[0])
  
# Function call
findPath(arr, M, N)
 
# This code is contributed by susmitakundugoaldanga.

C#

// C# program for the above approach
 
using System;
 
class GFG {
    // Function to find the row index for
    // every row of a matrix from which one
    // can exit the grid after entering from left
    static void findPath(int[, ] arr, int M, int N)
    {
        // Iterate over the range [0, M-1]
        for (int row = 0; row < M; row++) {
 
            // Stores the direction from
            // which a person enters a cell
            char dir = 'L';
 
            // Row index from which
            // one enters the grid
            int i = row;
 
            // Column index from which
            // one enters the grid
            int j = 0;
 
            // Iterate until j is atleast N-1
            while (j < N) {
 
                // If Mat[i][j] is equal to 1
                if (arr[i, j] == 1) {
 
                    // If entry is from left cell
                    if (dir == 'L') {
 
                        // Decrement i by 1
                        i--;
 
                        // Assign 'D' to dir
                        dir = 'D';
                    }
 
                    // If entry is from upper cell
                    else if (dir == 'U') {
                        // Decrement j by 1
                        j--;
                        // Assign 'R' to dir
                        dir = 'R';
                    }
                    // If entry is from right cell
                    else if (dir == 'R') {
 
                        // Increment i by 1
                        i++;
 
                        // Assign 'U' to dir
                        dir = 'U';
                    }
 
                    // If entry is from bottom cell
                    else if (dir == 'D') {
 
                        // Increment j by 1
                        j++;
 
                        // Assign 'L' to dir
                        dir = 'L';
                    }
                }
 
                // Otherwise,
                else {
                    // If entry is from left cell
                    if (dir == 'L') {
 
                        // Increment i by 1
                        i++;
 
                        // Assign 'U' to dir
                        dir = 'U';
                    }
 
                    // If entry is from upper cell
                    else if (dir == 'U') {
 
                        // Increment j by 1
                        j++;
 
                        // Assign 'L' to dir
                        dir = 'L';
                    }
 
                    // If entry is from right cell
                    else if (dir == 'R') {
 
                        // Decrement i by 1
                        i--;
 
                        // Assign 'D' to dir
                        dir = 'D';
                    }
                    // If entry is from lower cell
                    else if (dir == 'D') {
 
                        // Decrement j by 1
                        j--;
 
                        // Assign 'R' to dir
                        dir = 'R';
                    }
                }
 
                // If i or j is less than 0 or i is
                // equal to M or j is equal to N
                if (i < 0 || i == M || j < 0 || j == N)
                    break;
            }
 
            // If j is equal to N
            if (j == N)
                Console.Write(i + " ");
 
            // Otherwise
            else
                Console.Write(-1 + " ");
        }
    }
   
    // Driver Code
    public static void Main()
    {
       
        // Input
        int[, ] arr = { { 1, 1, 0, 1 },
                        { 1, 1, 0, 0 },
                        { 1, 0, 0, 0 },
                        { 1, 1, 0, 1 },
                        { 0, 1, 0, 1 } };
        int M = arr.GetLength(0);
        int N = arr.GetLength(1);
 
        // Function call
        findPath(arr, M, N);
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Function to find the row index for
// every row of a matrix from which one
// can exit the grid after entering from left
function findPath(arr, M, N)
{
      
    // Iterate over the range [0, M-1]
    for(let row = 0; row < M; row++)
    {
          
        // Stores the direction from
        // which a person enters a cell
        let dir = 'L';
  
        // Row index from which
        // one enters the grid
        let i = row;
  
        // Column index from which
        // one enters the grid
        let j = 0;
  
        // Iterate until j is atleast N-1
        while (j < N)
        {
              
            // If Mat[i][j] is equal to 1
            if (arr[i][j] == 1)
            {
  
                // If entry is from left cell
                if (dir == 'L')
                {
                      
                    // Decrement i by 1
                    i--;
  
                    // Assign 'D' to dir
                    dir = 'D';
                }
  
                // If entry is from upper cell
                else if (dir == 'U')
                {
                      
                    // Decrement j by 1
                    j--;
                      
                    // Assign 'R' to dir
                    dir = 'R';
                }
                  
                // If entry is from right cell
                else if (dir == 'R')
                {
                      
                    // Increment i by 1
                    i++;
  
                    // Assign 'U' to dir
                    dir = 'U';
                }
  
                // If entry is from bottom cell
                else if (dir == 'D')
                {
                      
                    // Increment j by 1
                    j++;
  
                    // Assign 'L' to dir
                    dir = 'L';
                }
            }
  
            // Otherwise,
            else
            {
                  
                // If entry is from left cell
                if (dir == 'L')
                {
                      
                    // Increment i by 1
                    i++;
  
                    // Assign 'U' to dir
                    dir = 'U';
                }
  
                // If entry is from upper cell
                else if (dir == 'U')
                {
                      
                    // Increment j by 1
                    j++;
  
                    // Assign 'L' to dir
                    dir = 'L';
                }
  
                // If entry is from right cell
                else if (dir == 'R')
                {
                      
                    // Decrement i by 1
                    i--;
  
                    // Assign 'D' to dir
                    dir = 'D';
                }
                  
                // If entry is from lower cell
                else if (dir == 'D')
                {
                      
                    // Decrement j by 1
                    j--;
  
                    // Assign 'R' to dir
                    dir = 'R';
                }
            }
  
            // If i or j is less than 0 or i is
            // equal to M or j is equal to N
            if (i < 0 || i == M || j < 0 || j == N)
                break;
        }
  
        // If j is equal to N
        if (j == N)
            document.write(i + " ");
  
        // Otherwise
        else
            document.write(-1 + " ");
    }
}
 
  
  // Driver Code
     
    // Input
    let arr = [[ 1, 1, 0, 1 ],
               [ 1, 1, 0, 0 ],
               [ 1, 0, 0, 0 ],
               [ 1, 1, 0, 1 ],
               [ 0, 1, 0, 1 ]];
    let M = arr.length;
    let N = arr[0].length;
  
    // Function call
    findPath(arr, M, N);
     
</script>