Given a matrix mat[][] of size N*M and the destination (x, y) to be reached from (0, 0), the task is to find if you can reach the destination following the given criteria:
- If the cell value is 0 you cannot move to that cell.
- If the cell value is 1, you can move to the cell and do not need to have any special value.
- In all other cases, you need to collect that value first before moving to that cell.
Movements in all four directions (up, down, left and right) are allowed and the positions where a specific value is situated are provided in a map name keys.
Input: mat = {{1, 0, 0, 0}, {1, 1, 1, 1}, {0, 2, 0, 0}, {1, 1, 1, 1}}
keys: {(1, 3): 2, (2, 1): 3}, x = 3, y = 1
Output: True
Explanation: In the above grid start from (0, 0) and
fetch the value 2 from (1, 3). Now move to (2, 1) and reach the destination (3, 1).Input: mat = {{1, 0, 0, 0}, {1, 1, 1, 1}, {0, 2, 0, 0}, {1, 1, 2, 1}}
keys: {(1, 3)=> 2, (2, 1)=> 3}, x = 3, y = 3
Output: True
Approach: The way to solve the problem is based on the concept of BFS:
We need to collect the values of the special cells with values greater than 1, thus Breadth-first traversal can be used to explore the closest levels first and move in all directions to collect the values and find path to reach the destination.
Follow the steps mentioned below to implement the idea:
- Perform Breadth-first traversal in grid starting from (0, 0). Three cases can arise:
- Case 1 (When a cell has a value of 1): In this case, we simply push this coordinate in the queue for exploring.
- Case 2 (When a cell needs a special value that is already collected): The cells that require the value can now be pushed into the queue for processing.
- Case 3 (When a cell needs a special value that is not yet collected). In this case, push this cell into a map that represents the cells that cannot be traversed in the absence of a value. When the value is found while traversing the grid, then visit all the rooms that are stored in the map which require this value.
- If the target room (x, y) is reached then return true otherwise false.
Below is the complete implementation of the above idea:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find if // the destination can be reached or not string Solvable(vector<vector<int> >& mat, map<pair<int, int>, int> Given_keys, int xDestination, int yDestination) { // Contains the keys which were found while // traversing the grid. set<int> ListOfAvailableKeys; ListOfAvailableKeys.insert(1); queue<vector<int> > q; q.push({ 0, 0 }); vector<vector<int> > dirr{ { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; // Contains value -> ListOfCells which // require this value. unordered_map<int, vector<pair<int, int> > > Unopened_Rooms; while (!q.empty()) { vector<int> curr = q.front(); q.pop(); // Checking if at the destination if (curr[0] == xDestination && curr[1] == yDestination) { return "True"; } // Case 2: If the current co-ordinate // contains any value. if (Given_keys.find({ curr[0], curr[1] }) != Given_keys.end()) { int curr_key = Given_keys[{ curr[0], curr[1] }]; // Insert the found value in // list of available values ListOfAvailableKeys.insert(curr_key); // Fetch the list of cells which require // the current value and then // push them in queue for exploration for (int i = 0; i < Unopened_Rooms[curr_key].size(); i++) { q.push( { Unopened_Rooms[curr_key][i].first, Unopened_Rooms[curr_key][i].second }); } } for (int i = 0; i < dirr.size(); i++) { int x = curr[0] + dirr[i][0]; int y = curr[1] + dirr[i][1]; if (x < 0 || y < 0 || x >= mat.size() || y >= mat[0].size() || mat[x][y] == 0) { continue; } // Case 3: if the cell requires a value // that currently we don't have. if (ListOfAvailableKeys.find(mat[x][y]) == ListOfAvailableKeys.end()) { Unopened_Rooms[(mat[x][y])].push_back( { x, y }); // Mark the cell as visited. mat[x][y] = 0; } else { q.push({ x, y }); // Mark that cell as visited. mat[x][y] = 0; } } } return "False"; } // Driver Code int main() { vector<vector<int> > mat{ { 1, 0, 0, 0 }, { 1, 1, 1, 1 }, { 0, 2, 0, 0 }, { 1, 1, 2, 1 } }; map<pair<int, int>, int> keys; keys[{ 1, 1 }] = 3; keys[{ 1, 3 }] = 2; int x = 3, y = 3; // Function Call cout << Solvable(mat, keys, x, y); return 0; } |
Python3
# Python3 code to implement the approach # Function to find if # the destination can be reached or not def Solvable(mat, Given_keys, xDestination, yDestination): # Contains the keys which were found while # traversing the grid. ListOfAvailableKeys = set() ListOfAvailableKeys.add(1) q = [] q.append([0, 0]) dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]] # Contains value -> ListOfCells which # require this value. Unopened_Rooms = {} while (len(q)): curr = q.pop(0) # Checking if at the destination if (curr[0] == xDestination and curr[1] == yDestination): return "True" # Case 2: If the current co-ordinate # contains any value. if ((curr[0], curr[1]) in Given_keys): curr_key = Given_keys[(curr[0], curr[1])] # Insert the found value in # list of available values ListOfAvailableKeys.add(curr_key) # Fetch the list of cells which require # the current value and then # push them in queue for exploration if curr_key in Unopened_Rooms: for i in range(len(Unopened_Rooms[curr_key])): q.append( (Unopened_Rooms[curr_key][i][0], Unopened_Rooms[curr_key][i][1])) for i in range(len(dirr)): x = curr[0] + dirr[i][0] y = curr[1] + dirr[i][1] if (x < 0 or y < 0 or x >= len(mat) or y >= len(mat[0]) or mat[x][y] == 0): continue # Case 3: if the cell requires a value # that currently we don't have. if (mat[x][y] not in ListOfAvailableKeys): if (mat[x][y] not in Unopened_Rooms): Unopened_Rooms[(mat[x][y])] = [] Unopened_Rooms[(mat[x][y])].append([x, y]) # Mark the cell as visited. mat[x][y] = 0 else: q.append([x, y]) # Mark that cell as visited. mat[x][y] = 0 return "False" # Driver Code mat = [[1, 0, 0, 0], [1, 1, 1, 1], [0, 2, 0, 0], [1, 1, 2, 1]] keys = {} keys[(1, 1)] = 3keys[(1, 3)] = 2x = 3y = 3 # Function Call print(Solvable(mat, keys, x, y)) # This code is contributed by phasing17 |
C#
// C# code to implement the approach using System; using System.Collections.Generic; class GFG { // Function to find if // the destination can be reached or not static string Solvable(int[, ] mat, Dictionary<string, int> Given_keys, int xDestination, int yDestination) { // Contains the keys which were found while // traversing the grid. HashSet<int> ListOfAvailableKeys = new HashSet<int>(); ListOfAvailableKeys.Add(1); List<int[]> q = new List<int[]>(); q.Add(new[] { 0, 0 }); int[, ] dirr = new int[, ] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; // Contains value -> ListOfCells which // require this value. Dictionary<int, List<int[]> > Unopened_Rooms = new Dictionary<int, List<int[]> >(); while (q.Count > 0) { int[] curr = q[0]; q.RemoveAt(0); // Checking if at the destination if (curr[0] == xDestination && curr[1] == yDestination) { return "True"; } // Case 2: If the current co-ordinate // contains any value. string key = Convert.ToString(curr[0]) + "#" + Convert.ToString(curr[1]); if (Given_keys.ContainsKey(key)) { int curr_key = Given_keys[key]; // Insert the found value in // list of available values ListOfAvailableKeys.Add(curr_key); // Fetch the list of cells which require // the current value and then // push them in queue for exploration if (Unopened_Rooms.ContainsKey(curr_key)) { for (var i = 0; i < Unopened_Rooms[curr_key].Count; i++) { q.Add(new[] { Unopened_Rooms[curr_key][i][0], Unopened_Rooms[curr_key][i][1] }); } } } for (int i = 0; i < dirr.GetLength(0); i++) { int x = curr[0] + dirr[i, 0]; int y = curr[1] + dirr[i, 1]; if (x < 0 || y < 0 || x >= mat.GetLength(0) || y >= mat.GetLength(1) || mat[x, y] == 0) { continue; } // Case 3: if the cell requires a value // that currently we don't have. if (!ListOfAvailableKeys.Contains(mat[x, y])) { if (!Unopened_Rooms.ContainsKey( mat[x, y])) Unopened_Rooms[(mat[x, y])] = new List<int[]>(); Unopened_Rooms[(mat[x, y])].Add(new[] { x, y }); // Mark the cell as visited. mat[x, y] = 0; } else { q.Add(new[] { x, y }); // Mark that cell as visited. mat[x, y] = 0; } } } return "False"; } // Driver Code public static void Main(string[] args) { int[, ] mat = new[, ] { { 1, 0, 0, 0 }, { 1, 1, 1, 1 }, { 0, 2, 0, 0 }, { 1, 1, 2, 1 } }; Dictionary<string, int> keys = new Dictionary<string, int>(); keys["1#1"] = 3; keys["1#3"] = 2; int x = 3; int y = 3; // Function Call Console.WriteLine(Solvable(mat, keys, x, y)); } } // This code is contributed by phasing17 |
Javascript
// JavaScript code to implement the approach // Function to find if // the destination can be reached or not function Solvable(mat, Given_keys, xDestination, yDestination) { // Contains the keys which were found while // traversing the grid. let ListOfAvailableKeys = new Set(); ListOfAvailableKeys.add(1); let q = []; q.push([ 0, 0 ]); let dirr = [ [ 1, 0 ], [ 0, 1 ], [ -1, 0 ], [ 0, -1 ] ]; // Contains value -> ListOfCells which // require this value. let Unopened_Rooms = {}; while (q.length) { let curr = q.shift(); // Checking if at the destination if (curr[0] == xDestination && curr[1] == yDestination) { return "True"; } // Case 2: If the current co-ordinate // contains any value. if (Given_keys.hasOwnProperty( [ curr[0], curr[1] ])) { let curr_key = Given_keys [[curr [0], curr [1]]]; // Insert the found value in // list of available values ListOfAvailableKeys.add(curr_key); // Fetch the list of cells which require // the current value and then // push them in queue for exploration if (Unopened_Rooms.hasOwnProperty(curr_key)) { for (var i = 0; i < Unopened_Rooms[curr_key].length; i++) { q.push([ Unopened_Rooms[curr_key][i][0], Unopened_Rooms[curr_key][i][1] ]); } } } for (let i = 0; i < dirr.length; i++) { let x = curr[0] + dirr[i][0]; let y = curr[1] + dirr[i][1]; if (x < 0 || y < 0 || x >= mat.length || y >= mat[0].length || mat[x][y] == 0) { continue; } // Case 3: if the cell requires a value // that currently we don't have. if (!ListOfAvailableKeys.has(mat[x][y])) { if (!Unopened_Rooms.hasOwnProperty( mat[x][y])) Unopened_Rooms[(mat[x][y])] = []; Unopened_Rooms[(mat[x][y])].push([ x, y ]); // Mark the cell as visited. mat[x][y] = 0; } else { q.push([ x, y ]); // Mark that cell as visited. mat[x][y] = 0; } } } return "False"; } // Driver Code let mat = [ [ 1, 0, 0, 0 ], [ 1, 1, 1, 1 ], [ 0, 2, 0, 0 ], [ 1, 1, 2, 1 ] ]; let keys = {}; keys[[ 1, 1 ]] = 3; keys[[ 1, 3 ]] = 2; let x = 3; let y = 3; // Function Call console.log(Solvable(mat, keys, x, y)); // This code is contributed by phasing17 |
Java
import java.util.*; // java code to implement the approach // Function to find if // the destination can be reached or not public class Solvable { public static boolean isSolvable(int[][] mat, Map<List<Integer>, Integer> givenKeys, int xDestination, int yDestination) { Set<Integer> listOfAvailableKeys = new HashSet<>(); listOfAvailableKeys.add(1); Queue<List<Integer> > q = new LinkedList<>(); q.offer(Arrays.asList(0, 0)); int[][] dirr = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } }; // Contains value -> ListOfCells which // require this value. Map<Integer, List<List<Integer> > > unopenedRooms = new HashMap<>(); while (!q.isEmpty()) { List<Integer> curr = q.poll(); // Checking if at the destination if (curr.get(0) == xDestination && curr.get(1) == yDestination) { return true; } // Case 2: If the current co-ordinate // contains any value. if (givenKeys.containsKey(curr)) { int currKey = givenKeys.get(curr); // Insert the found value in // list of available values listOfAvailableKeys.add(currKey); // Fetch the list of cells which require // the current value and then // push them in queue for exploration if (unopenedRooms.containsKey(currKey)) { for (List<Integer> room : unopenedRooms.get(currKey)) { q.offer(room); } } } for (int i = 0; i < dirr.length; i++) { int x = curr.get(0) + dirr[i][0]; int y = curr.get(1) + dirr[i][1]; if (x < 0 || y < 0 || x >= mat.length || y >= mat[0].length || mat[x][y] == 0) { continue; } // Case 3: if the cell requires a value // that currently we don't have. if (!listOfAvailableKeys.contains( mat[x][y])) { if (!unopenedRooms.containsKey( mat[x][y])) { unopenedRooms.put( mat[x][y], new ArrayList<>()); } unopenedRooms.get(mat[x][y]).add( Arrays.asList(x, y)); // Mark the cell as visited. mat[x][y] = 0; } else { q.offer(Arrays.asList(x, y)); // Mark that cell as visited. mat[x][y] = 0; } } } return false; } // Driver code public static void main(String[] args) { int[][] mat = { { 1, 0, 0, 0 }, { 1, 1, 1, 1 }, { 0, 2, 0, 0 }, { 1, 1, 2, 1 } }; Map<List<Integer>, Integer> keys = new HashMap<>(); keys.put(Arrays.asList(1, 1), 3); keys.put(Arrays.asList(1, 3), 2); int x = 3; int y = 3; // Function call System.out.println(isSolvable(mat, keys, x, y)); } } // This code is contributed by NarasingaNikhil |
Output
True
Time Complexity: O(N * M)
Auxiliary Space: 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!
