Given a grid of size N X M and a robot is placed at cell (N – 1, M – 1). Also, given string str which consists only of the characters ‘U’ (Up), ‘D’ (Down), ‘L’ (Left) and ‘R’ (Right) representing the moves the robot is going to perform within the grid. The task is to find whether the robot will be safe at the end of the last move. Robot is said to be safe if it is within the bounds of the grid.
Note: Consider that the rectangular grid is present below the number line with the top-left corner lying on the origin.
Examples:
Input: N = 1, M = 1, str = “R”
Output: No
As there is only 1 cell, no movement is allowed.
Input: N = 2, M = 3, str = “LLRU”
Output: Yes
Approach: For every move, update the position of the robot inside the grid. if at any move the position of the robot is outside the grid then the output will be No else print Yes if for all the moves, the robot is within the bounds of the grid.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function that returns true if the robot is safebool isSafe(int N, int M, string str){ int coll = 0, colr = 0, rowu = 0, rowd = 0; for (int i = 0; i < str.length(); i++) { // If current move is "L" then // increase the counter of coll if (str[i] == 'L') { coll++; if (colr > 0) { colr--; } // If value of coll is equal to // column then break if (coll == M) { break; } } // If current move is "R" then // increase the counter of colr else if (str[i] == 'R') { colr++; if (coll > 0) { coll--; } // If value of colr is equal to // column then break if (colr == M) { break; } } // If current move is "U" then // increase the counter of rowu else if (str[i] == 'U') { -rowu++; if (rowd > 0) { rowd--; } // If value of rowu is equal to // row then break if (rowu == N) { break; } } // If current move is "D" then // increase the counter of rowd else if (str[i] == 'D') { rowd++; if (rowu > 0) { rowu--; } // If value of rowd is equal to // row then break if (rowd == N) { break; } } } // If robot is within the bounds of the grid if (abs(rowd) < N && abs(rowu) < N && abs(coll) < M && abs(colr) < M) { return true; } // Unsafe return false;}// Driver codeint main(){ int N = 1, M = 1; string str = "R"; if (isSafe(N, M, str)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approachclass GFG { // Function that returns true if the robot is safe static boolean isSafe(int N, int M, char[] str) { int coll = 0, colr = 0, rowu = 0, rowd = 0; for (int i = 0; i < str.length; i++) { // If current move is "L" then // increase the counter of coll if (str[i] == 'L') { coll++; if (colr > 0) { colr--; } // If value of coll is equal to // column then break if (coll == M) { break; } } // If current move is "R" then // increase the counter of colr else if (str[i] == 'R') { colr++; if (coll > 0) { coll--; } // If value of colr is equal to // column then break if (colr == M) { break; } } // If current move is "U" then // increase the counter of rowu else if (str[i] == 'U') { rowu++; if (rowd > 0) { rowd--; } // If value of rowu is equal to // row then break if (rowu == N) { break; } } // If current move is "D" then // increase the counter of rowd else if (str[i] == 'D') { rowd++; if (rowu > 0) { rowu--; } // If value of rowd is equal to // row then break if (rowd == N) { break; } } } // If robot is within the bounds of the grid if (Math.abs(rowd) < N && Math.abs(rowu) < N && Math.abs(coll) < M && Math.abs(colr) < M) { return true; } // Unsafe return false; } // Driver code public static void main(String[] args) { int N = 1, M = 1; String str = "R"; if (isSafe(N, M, str.toCharArray())) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by 29AjayKumar |
Python3
# Python 3 implementation of the approach# Function that returns true # if the robot is safedef isSafe(N, M, str): coll = 0 colr = 0 rowu = 0 rowd = 0 for i in range(len(str)): # If current move is "L" then # increase the counter of coll if (str[i] == 'L'): coll += 1 if (colr > 0): colr -= 1 # If value of coll is equal to # column then break if (coll == M): break # If current move is "R" then # increase the counter of colr elif (str[i] == 'R'): colr += 1 if (coll > 0): coll -= 1 # If value of colr is equal to # column then break if (colr == M): break # If current move is "U" then # increase the counter of rowu elif (str[i] == 'U'): rowu += 1 if (rowd > 0): rowd -= 1 # If value of rowu is equal to # row then break if (rowu == N): break # If current move is "D" then # increase the counter of rowd elif (str[i] == 'D'): rowd += 1 if (rowu > 0): rowu -= 1 # If value of rowd is equal to # row then break if (rowd == N): break # If robot is within the bounds of the grid if (abs(rowd) < N and abs(rowu) < N and abs(coll) < M and abs(colr) < M): return True # Unsafe return False# Driver codeif __name__ == '__main__': N = 1 M = 1 str = "R" if (isSafe(N, M, str)): print("Yes") else: print("No")# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG { // Function that returns true if the robot is safe static bool isSafe(int N, int M, char[] str) { int coll = 0, colr = 0, rowu = 0, rowd = 0; for (int i = 0; i < str.Length; i++) { // If current move is "L" then // increase the counter of coll if (str[i] == 'L') { coll++; if (colr > 0) { colr--; } // If value of coll is equal to // column then break if (coll == M) { break; } } // If current move is "R" then // increase the counter of colr else if (str[i] == 'R') { colr++; if (coll > 0) { coll--; } // If value of colr is equal to // column then break if (colr == M) { break; } } // If current move is "U" then // increase the counter of rowu else if (str[i] == 'U') { rowu++; if (rowd > 0) { rowd--; } // If value of rowu is equal to // row then break if (rowu == N) { break; } } // If current move is "D" then // increase the counter of rowd else if (str[i] == 'D') { rowd++; if (rowu > 0) { rowu--; } // If value of rowd is equal to // row then break if (rowd == N) { break; } } } // If robot is within the bounds of the grid if (Math.Abs(rowd) < N && Math.Abs(rowu) < N && Math.Abs(coll) < M && Math.Abs(colr) < M) { return true; } // Unsafe return false; } // Driver code public static void Main(String[] args) { int N = 1, M = 1; String str = "R"; if (isSafe(N, M, str.ToCharArray())) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code has been contributed by 29AjayKumar |
Javascript
<script>// Javascript implementation of the approach// Function that returns true if the robot is safefunction isSafe(N, M, str){ var coll = 0, colr = 0, rowu = 0, rowd = 0; for (var i = 0; i < str.length; i++) { // If current move is "L" then // increase the counter of coll if (str[i] == 'L') { coll++; if (colr > 0) { colr--; } // If value of coll is equal to // column then break if (coll == M) { break; } } // If current move is "R" then // increase the counter of colr else if (str[i] == 'R') { colr++; if (coll > 0) { coll--; } // If value of colr is equal to // column then break if (colr == M) { break; } } // If current move is "U" then // increase the counter of rowu else if (str[i] == 'U') { -rowu++; if (rowd > 0) { rowd--; } // If value of rowu is equal to // row then break if (rowu == N) { break; } } // If current move is "D" then // increase the counter of rowd else if (str[i] == 'D') { rowd++; if (rowu > 0) { rowu--; } // If value of rowd is equal to // row then break if (rowd == N) { break; } } } // If robot is within the bounds of the grid if (Math.abs(rowd) < N && Math.abs(rowu) < N && Math.abs(coll) < M && Math.abs(colr) < M) { return true; } // Unsafe return false;}// Driver codevar N = 1, M = 1;var str = "R";if (isSafe(N, M, str)) document.write( "Yes");else document.write( "No");</script> |
Output:
No
Time Complexity: O(|str|)
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!
