Given a N x M matrix. Each cell of the matrix has a numerical value pointing to the next cell it leads to. The values of matrix[i][j] can be:
- 1 which means go to the cell to the right. (i.e. go from matrix[i][j] to matrix[i][j + 1])
- 2 which means go to the cell to the left. (i.e. go from matrix[i][j] to matrix[i][j – 1])
- 3 which means go to the lower cell. (i.e. go from matrix[i][j] to matrix[i + 1][j])
- 4 which means go to the upper cell. (i.e. go from matrix[i][j] to matrix[i – 1][j])
Source cell (x1, y1) and destination cell (x2, y2) are given. The task is to find whether a path exists between the given source cell and the destination cell.
Examples:
Input: matrix[][] = {{3, 2, 2, 2}, {3, 4, 2, 3}, {1, 3, 4, 4}, {2, 1, 1, 2}, {4, 4, 3, 3}}, source cell = {0, 3}, destination cell = {3, 1}
Output: Yes
3 2 2 2 3 4 2 3 1 3 4 4 2 1 1 2 4 4 3 3 Explanation : Starting from cell (0, 3), follow the path based on the direction rule. Traverse the cells in the following order: (0, 3)->(0, 2)->(0, 1)->(0, 0)->(1, 0)->(2, 0)->(2, 1)->(3, 1) which is the destination.
Input: matrix[][]={{1, 4, 3}, {2, 3, 2}, {4, 1, 4}}, source cell = {1, 1}, destination cell = {0, 3}
Output: No
1 4 3 2 3 2 4 1 4 Explanation: Starting from cell (1, 1), follow the path based on the direction rule. Traverse the cells as: (1, 1)->(2, 1)->(2, 2)->(1, 2)->(1, 1), here source cell is visited again and thus in any case destination cell is not visited.
Approach: The task can be solved by using either DFS or BFS.
- It can be observed that the path to be followed is fixed and we need to traverse the matrix based on the assigned direction rule.
- Start either DFS or BFS from the source cell and move according to the direction rule described above.
- If the destination cell is reached, a valid path is found.
- If a visited cell is revisited again or the current cell’s indices goes out of the range, then the destination cell is not reached through that path, else continue.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check whether a valid path// exists or notbool uniquepath(vector<vector<int> >& matrix, int curr_x, int curr_y, int dest_x, int dest_y, vector<vector<bool> >& visited){ // Check if destination cell is reached if (curr_x == dest_x && curr_y == dest_y) return true; // Base Cases if (!(curr_x >= 0 && curr_x < matrix.size() && curr_y >= 0 && curr_y < matrix[0].size())) return false; // Check whether a visited cell is // re-visited again if (visited[curr_x][curr_y] == true) return false; // Mark current cell as visited visited[curr_x][curr_y] = true; // Moving based on direction rule if (matrix[curr_x][curr_y] == 1) return uniquepath(matrix, curr_x, curr_y + 1, dest_x, dest_y, visited); else if (matrix[curr_x][curr_y] == 2) return uniquepath(matrix, curr_x, curr_y - 1, dest_x, dest_y, visited); else if (matrix[curr_x][curr_y] == 3) return uniquepath(matrix, curr_x + 1, curr_y, dest_x, dest_y, visited); else if (matrix[curr_x][curr_y] == 4) return uniquepath(matrix, curr_x - 1, curr_y, dest_x, dest_y, visited);}// Driver codeint main(){ vector<vector<int> > matrix = { { 3, 2, 2, 2 }, { 3, 4, 2, 3 }, { 1, 3, 4, 4 }, { 2, 1, 1, 2 }, { 4, 4, 1, 2 } }; int start_x = 0, start_y = 3; int dest_x = 3, dest_y = 1; int n = matrix.size(); int m = matrix[0].size(); vector<vector<bool> > visited( n, vector<bool>(m, false)); if (uniquepath(matrix, start_x, start_y, dest_x, dest_y, visited)) cout << "Yes"; else cout << "No";} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to check whether a valid path// exists or notstatic boolean uniquepath(int[][]matrix, int curr_x, int curr_y, int dest_x, int dest_y, boolean[][] visited){ // Check if destination cell is reached if (curr_x == dest_x && curr_y == dest_y) return true; // Base Cases if (!(curr_x >= 0 && curr_x < matrix.length && curr_y >= 0 && curr_y < matrix[0].length)) return false; // Check whether a visited cell is // re-visited again if (visited[curr_x][curr_y] == true) return false; // Mark current cell as visited visited[curr_x][curr_y] = true; // Moving based on direction rule if (matrix[curr_x][curr_y] == 1) return uniquepath(matrix, curr_x, curr_y + 1, dest_x, dest_y, visited); else if (matrix[curr_x][curr_y] == 2) return uniquepath(matrix, curr_x, curr_y - 1, dest_x, dest_y, visited); else if (matrix[curr_x][curr_y] == 3) return uniquepath(matrix, curr_x + 1, curr_y, dest_x, dest_y, visited); else if (matrix[curr_x][curr_y] == 4) return uniquepath(matrix, curr_x - 1, curr_y, dest_x, dest_y, visited); return false;}// Driver codepublic static void main(String[] args){ int[][] matrix = { { 3, 2, 2, 2 }, { 3, 4, 2, 3 }, { 1, 3, 4, 4 }, { 2, 1, 1, 2 }, { 4, 4, 1, 2 } }; int start_x = 0, start_y = 3; int dest_x = 3, dest_y = 1; int n = matrix.length; int m = matrix[0].length; boolean[][] visited = new boolean[n][m]; if (uniquepath(matrix, start_x, start_y, dest_x, dest_y, visited)) System.out.print("Yes"); else System.out.print("No");}}// This code is contributed by 29AjayKumar |
Python3
# python program for the above approach# Function to check whether a valid path# exists or notdef uniquepath(matrix, curr_x, curr_y, dest_x, dest_y, visited): # Check if destination cell is reached if (curr_x == dest_x and curr_y == dest_y): return True # Base Cases if (not(curr_x >= 0 and curr_x < len(matrix) and curr_y >= 0 and curr_y < len(matrix[0]))): return False # Check whether a visited cell is # re-visited again if (visited[curr_x][curr_y] == True): return False # Mark current cell as visited visited[curr_x][curr_y] = True # Moving based on direction rule if (matrix[curr_x][curr_y] == 1): return uniquepath(matrix, curr_x, curr_y + 1, dest_x, dest_y, visited) elif (matrix[curr_x][curr_y] == 2): return uniquepath(matrix, curr_x, curr_y - 1, dest_x, dest_y, visited) elif (matrix[curr_x][curr_y] == 3): return uniquepath(matrix, curr_x + 1, curr_y, dest_x, dest_y, visited) elif (matrix[curr_x][curr_y] == 4): return uniquepath(matrix, curr_x - 1, curr_y, dest_x, dest_y, visited)# Driver codeif __name__ == "__main__": matrix = [[3, 2, 2, 2], [3, 4, 2, 3], [1, 3, 4, 4], [2, 1, 1, 2], [4, 4, 1, 2] ] start_x = 0 start_y = 3 dest_x = 3 dest_y = 1 n = len(matrix) m = len(matrix[0]) visited = [[False for _ in range(m)] for _ in range(n)] if (uniquepath(matrix, start_x, start_y, dest_x, dest_y, visited)): print("Yes") else: print("No") # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;public class GFG{// Function to check whether a valid path// exists or notstatic bool uniquepath(int[,]matrix, int curr_x, int curr_y, int dest_x, int dest_y, bool[,] visited){ // Check if destination cell is reached if (curr_x == dest_x && curr_y == dest_y) return true; // Base Cases if (!(curr_x >= 0 && curr_x < matrix.GetLength(0) && curr_y >= 0 && curr_y < matrix.GetLength(1))) return false; // Check whether a visited cell is // re-visited again if (visited[curr_x,curr_y] == true) return false; // Mark current cell as visited visited[curr_x,curr_y] = true; // Moving based on direction rule if (matrix[curr_x,curr_y] == 1) return uniquepath(matrix, curr_x, curr_y + 1, dest_x, dest_y, visited); else if (matrix[curr_x,curr_y] == 2) return uniquepath(matrix, curr_x, curr_y - 1, dest_x, dest_y, visited); else if (matrix[curr_x,curr_y] == 3) return uniquepath(matrix, curr_x + 1, curr_y, dest_x, dest_y, visited); else if (matrix[curr_x,curr_y] == 4) return uniquepath(matrix, curr_x - 1, curr_y, dest_x, dest_y, visited); return false;}// Driver codepublic static void Main(String[] args){ int[,] matrix = { { 3, 2, 2, 2 }, { 3, 4, 2, 3 }, { 1, 3, 4, 4 }, { 2, 1, 1, 2 }, { 4, 4, 1, 2 } }; int start_x = 0, start_y = 3; int dest_x = 3, dest_y = 1; int n = matrix.GetLength(0); int m = matrix.GetLength(1); bool[,] visited = new bool[n,m]; if (uniquepath(matrix, start_x, start_y, dest_x, dest_y, visited)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to check whether a valid path// exists or notfunction uniquepath(matrix, curr_x, curr_y, dest_x, dest_y, visited){ // Check if destination cell is reached if (curr_x == dest_x && curr_y == dest_y) return true; // Base Cases if ( !( curr_x >= 0 && curr_x < matrix.length && curr_y >= 0 && curr_y < matrix[0].length ) ) return false; // Check whether a visited cell is // re-visited again if (visited[curr_x][curr_y] == true) return false; // Mark current cell as visited visited[curr_x][curr_y] = true; // Moving based on direction rule if (matrix[curr_x][curr_y] == 1) return uniquepath(matrix, curr_x, curr_y + 1, dest_x, dest_y, visited); else if (matrix[curr_x][curr_y] == 2) return uniquepath(matrix, curr_x, curr_y - 1, dest_x, dest_y, visited); else if (matrix[curr_x][curr_y] == 3) return uniquepath(matrix, curr_x + 1, curr_y, dest_x, dest_y, visited); else if (matrix[curr_x][curr_y] == 4) return uniquepath(matrix, curr_x - 1, curr_y, dest_x, dest_y, visited);}// Driver codelet matrix = [ [3, 2, 2, 2], [3, 4, 2, 3], [1, 3, 4, 4], [2, 1, 1, 2], [4, 4, 1, 2],];let start_x = 0, start_y = 3;let dest_x = 3, dest_y = 1;let n = matrix.length;let m = matrix[0].length;let visited = new Array(n).fill(0).map(() => new Array(m).fill(false));if (uniquepath(matrix, start_x, start_y, dest_x, dest_y, visited)) document.write("Yes");else document.write("No");// This code is contributed by gfgking.</script> |
Output
Yes
Time Complexity: O(n*m)
Auxiliary Space: O(n*m)
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!
