Given a binary matrix of dimensions N * M, the task is to find the indices of the matrix such that traversal of the given matrix from the cell (0, 0) leads to outside the matrix as per the following conditions:
- If the value of arr[i][j] is 0, then traverse in the same direction and check the next value.
- If the value of arr[i][j] is 1, then update arr[i][j] to 0 and change the current direction from up, right, down, or left to the directions right, down, left, and up respectively.
Examples:
Input: arr[] = {{0, 1}, {1, 0}}
Output: (1, 1)
Explanation:
Below is the image to illustrate the simulation:
Input: arr[] = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 1, 0, 0}}
Output: (2, 0)
Approach: Follow the steps below to solve the problem:
-
- Initialize two variables, say current_i and current_j, both as 0.
- Traverse the matrix from the index (0, 0) and set the current direction as a right as R.
- If the value of current_i or current_j is N or M respectively, then perform the following operations:
- If the value of arr[i][j] is 0, then traverse in the same direction and check the next value.
- Otherwise, update arr[i][j] to 0 and choose a direction that is right to the current direction. If the direction which is right to the current direction is:
- L: Move the current row backward i.e., j – 1.
- R: Move the current row forwards i.e., j + 1.
- U: Move the current column upwards i.e., i – 1.
- D: Move the current column downwards i.e., i + 1.
- If the new coordinates are not within the range, then print the current coordinates as the resulting coordinates and break out of the loop.
C++
// CPP program for the above approach #include<bits/stdc++.h>using namespace std;// Function to check if the indices (i, j) // are valid indices in a Matrix or not bool issafe(int m, int n, int i, int j){ // Cases for invalid cells if (i < 0) return false; if (j < 0) return false; if (i >= m) return false; if (j >= n) return false; // Return true if valid return true;}// Function to find indices of cells // of a matrix from which traversal // leads to out of the matrix pair<int,int> endpoints(vector<vector<int>> arr, int m, int n){ // Starting from cell (0, 0), // traverse in right direction int i = 0; int j = 0; int current_i = 0; int current_j = 0; char current_d = 'r'; // Stores direction changes map<char,char> rcd = {{'l', 'u'},{'u', 'r'}, {'r', 'd'}, {'d', 'l'}}; // Iterate until the current cell // exceeds beyond the matrix while (issafe(m, n, i, j)){ // Current index current_i = i; current_j = j; // If the current cell is 1 if (arr[i][j] == 1){ char move_in = rcd[current_d]; // Update arr[i][j] = 0 arr[i][j] = 0; // Update indices according // to the direction if (move_in == 'u') i -= 1; else if(move_in == 'd') i += 1; else if(move_in == 'l') j -= 1; else if(move_in == 'r') j += 1; current_d = move_in; } // Otherwise else{ // Update indices according // to the direction if (current_d == 'u') i -= 1; else if(current_d == 'd') i += 1; else if(current_d == 'l') j -= 1; else if(current_d == 'r') j += 1; } } // The exit coordinates return {current_i, current_j}; } // Driver Codeint main(){ // Number of rows int M = 3; // Number of columns int N = 5; // Given matrix arr[][] vector<vector<int>> arr{{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 1, 0, 0}}; pair<int,int> p = endpoints(arr, M, N); cout << "(" << p.first << ", " << p.second << ")" << endl; } // This code is contributed by ipg2016107. |
Java
// JAVA program for the above approach import java.util.HashMap;import java.util.Map;class GFG{// Function to check if the indices (i, j) // are valid indices in a Matrix or not static boolean issafe(int m, int n, int i, int j){ // Cases for invalid cells if (i < 0) return false; if (j < 0) return false; if (i >= m) return false; if (j >= n) return false; // Return true if valid return true;}// Function to find indices of cells // of a matrix from which traversal // leads to out of the matrix static int [] endpoints(int [][]arr, int m, int n){ // Starting from cell (0, 0), // traverse in right direction int i = 0; int j = 0; int current_i = 0; int current_j = 0; char current_d = 'r'; // Stores direction changes Map<Character,Character> rcd = new HashMap<>(); rcd.put('l', 'u'); rcd.put('u', 'r'); rcd.put('r', 'd'); rcd.put('d', 'l'); // Iterate until the current cell // exceeds beyond the matrix while (issafe(m, n, i, j)){ // Current index current_i = i; current_j = j; // If the current cell is 1 if (arr[i][j] == 1){ char move_in = rcd.get(current_d); // Update arr[i][j] = 0 arr[i][j] = 0; // Update indices according // to the direction if (move_in == 'u') i -= 1; else if(move_in == 'd') i += 1; else if(move_in == 'l') j -= 1; else if(move_in == 'r') j += 1; current_d = move_in; } // Otherwise else{ // Update indices according // to the direction if (current_d == 'u') i -= 1; else if(current_d == 'd') i += 1; else if(current_d == 'l') j -= 1; else if(current_d == 'r') j += 1; } } // The exit coordinates return new int[]{current_i, current_j}; } // Driver Codepublic static void main(String[] args){ // Number of rows int M = 3; // Number of columns int N = 5; // Given matrix arr[][] int [][]arr = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 1, 0, 0}}; int []p = endpoints(arr, M, N); System.out.print("(" + p[0]+ ", " + p[1]+ ")" +"\n"); }} // This code is contributed by shikhasingrajput |
Python3
# Python program for the above approach # Function to check if the indices (i, j) # are valid indices in a Matrix or not def issafe(m, n, i, j): # Cases for invalid cells if i < 0: return False if j < 0: return False if i >= m: return False if j >= n: return False # Return true if valid return True # Function to find indices of cells # of a matrix from which traversal # leads to out of the matrix def endpoints(arr, m, n): # Starting from cell (0, 0), # traverse in right direction i = 0 j = 0 current_d = 'r' # Stores direction changes rcd = {'l': 'u', 'u': 'r', 'r': 'd', 'd': 'l'} # Iterate until the current cell # exceeds beyond the matrix while issafe(m, n, i, j): # Current index current_i = i current_j = j # If the current cell is 1 if arr[i][j] == 1: move_in = rcd[current_d] # Update arr[i][j] = 0 arr[i][j] = 0 # Update indices according # to the direction if move_in == 'u': i -= 1 elif move_in == 'd': i += 1 elif move_in == 'l': j -= 1 elif move_in == 'r': j += 1 current_d = move_in # Otherwise else: # Update indices according # to the direction if current_d == 'u': i -= 1 elif current_d == 'd': i += 1 elif current_d == 'l': j -= 1 elif current_d == 'r': j += 1 # The exit coordinates return (current_i, current_j) # Driver Code # Number of rows M = 3 # Number of columns N = 5 # Given matrix arr[][] arr = [[0, 1, 1, 1, 0], [1, 0, 1, 0, 1], [1, 1, 1, 0, 0], ] print(endpoints(arr, M, N)) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to check if the indices (i, j) // are valid indices in a Matrix or not static bool issafe(int m, int n, int i, int j) { // Cases for invalid cells if (i < 0) return false; if (j < 0) return false; if (i >= m) return false; if (j >= n) return false; // Return true if valid return true; } // Function to find indices of cells // of a matrix from which traversal // leads to out of the matrix static int[] endpoints(int[, ] arr, int m, int n) { // Starting from cell (0, 0), // traverse in right direction int i = 0; int j = 0; int current_i = 0; int current_j = 0; char current_d = 'r'; // Stores direction changes Dictionary<char, char> rcd = new Dictionary<char, char>(); rcd['l'] = 'u'; rcd['u'] = 'r'; rcd['r'] = 'd'; rcd['d'] = 'l'; // Iterate until the current cell // exceeds beyond the matrix while (issafe(m, n, i, j)) { // Current index current_i = i; current_j = j; // If the current cell is 1 if (arr[i, j] == 1) { char move_in = rcd[current_d]; // Update arr[i][j] = 0 arr[i, j] = 0; // Update indices according // to the direction if (move_in == 'u') i -= 1; else if (move_in == 'd') i += 1; else if (move_in == 'l') j -= 1; else if (move_in == 'r') j += 1; current_d = move_in; } // Otherwise else { // Update indices according // to the direction if (current_d == 'u') i -= 1; else if (current_d == 'd') i += 1; else if (current_d == 'l') j -= 1; else if (current_d == 'r') j += 1; } } // The exit coordinates return new int[] { current_i, current_j }; } // Driver Code public static void Main(string[] args) { // Number of rows int M = 3; // Number of columns int N = 5; // Given matrix arr[][] int[, ] arr = { { 0, 1, 1, 1, 0 }, { 1, 0, 1, 0, 1 }, { 1, 1, 1, 0, 0 } }; int[] p = endpoints(arr, M, N); Console.WriteLine("(" + p[0] + ", " + p[1] + ")" + "\n"); }}// This code is contributed by ukasp. |
Javascript
<script>// JavaScript program for the above approach// Function to check if the indices (i, j)// are valid indices in a Matrix or notfunction issafe(m,n,i,j){ // Cases for invalid cells if (i < 0) return false; if (j < 0) return false; if (i >= m) return false; if (j >= n) return false; // Return true if valid return true;}// Function to find indices of cells// of a matrix from which traversal// leads to out of the matrixfunction endpoints(arr,m,n){ // Starting from cell (0, 0), // traverse in right direction let i = 0; let j = 0; let current_i = 0; let current_j = 0; let current_d = 'r'; // Stores direction changes let rcd = new Map(); rcd.set('l', 'u'); rcd.set('u', 'r'); rcd.set('r', 'd'); rcd.set('d', 'l'); // Iterate until the current cell // exceeds beyond the matrix while (issafe(m, n, i, j)){ // Current index current_i = i; current_j = j; // If the current cell is 1 if (arr[i][j] == 1){ let move_in = rcd.get(current_d); // Update arr[i][j] = 0 arr[i][j] = 0; // Update indices according // to the direction if (move_in == 'u') i -= 1; else if(move_in == 'd') i += 1; else if(move_in == 'l') j -= 1; else if(move_in == 'r') j += 1; current_d = move_in; } // Otherwise else{ // Update indices according // to the direction if (current_d == 'u') i -= 1; else if(current_d == 'd') i += 1; else if(current_d == 'l') j -= 1; else if(current_d == 'r') j += 1; } } // The exit coordinates return [current_i, current_j];}// Driver Code// Number of rowslet M = 3;// Number of columnslet N = 5;// Given matrix arr[][]let arr = [[0, 1, 1, 1, 0],[1, 0, 1, 0, 1],[1, 1, 1, 0, 0]];let p = endpoints(arr, M, N);document.write("(" + p[0]+ ", " + p[1]+ ")" +"\n");// This code is contributed by avanitrachhadiya2155</script> |
Output
(2, 0)
Time complexity: O(m * n)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
