Restricted movement to reach the given point on a board
Given a board of size 401×401 and 2 integers a and b. There is a person standing at position (0, 0), and the person has to reach (a, b) in minimum operations such that man is allowed to make only operations Left, Right, Top, Bottom, and Stand still. The person is not allowed to repeat the previous operation, if the person uses upward operations then he cannot use upward again as the next operation. Moreover, the person cannot move out of the board
Examples:
Input: a = 4, b = 4
Output: 8
Explanation: alternating using operations “go right” and “go up”. Repeat this four times.Input: a = 2, b = 3
Output: 5
Approach: This can be solved with the following idea:
- Let |a| = |b|, then If the person alternates between moves along rows and moves along columns, it can reach (a, b) in 2 * |a| moves.
- Let |a| ≠ |b|, specifically a > b ≥ 0 (without loss of generality due to the board symmetry). In 2a – 1 moves, the person can reach (a, b). It subsequently moves in the direction of a on turns 1, 3, 5, …, 2a – 1. To get to b, use the remaining a-1 moves. The final option is to use “skip” moves to fill the remaining slots.
- As a result, the solution is |a| + |b| if |a| = |b| and 2 * max(|a|, |b|) – 1 in all other cases.
Below are the steps involved in the implementation of the code:
- If |a| = |b|, return 2 * a
- Else, 2 * max(a, b) – 1
Below is the Implementation of the above approach:
C++
// C++ code for the above approach #include <iostream> using namespace std; // Function to count minimum operations // Required int minOperations( int a, int b) { if (a == b) { return 2 * a; } else { return 2 * max(a, b) - 1; } } // Driver code int main() { int a = 4; int b = 4; // Function call cout << minOperations(a, b); return 0; } |
Java
public class Main { // Function to count minimum operations // Required public static int minOperations( int a, int b) { if (a == b) { return 2 * a; } else { return 2 * Math.max(a, b) - 1 ; } } // Driver code public static void main(String[] args) { int a = 4 ; int b = 4 ; // Function call System.out.println(minOperations(a, b)); } } // This code is contributed by Prajwal Kandekar |
Python3
# Function to count minimum operations Required def minOperations(a,b): if (a = = b): return 2 * a else : return 2 * max (a,b) - 1 # Driver code a = 4 b = 4 # Function Call print (minOperations(a,b)) # This Code is Contributed By Vikas Bishnoi |
C#
// C# code for the above approach using System; public class GFG { // function to count minimum operations Required static int minOperations( int a, int b) { if (a == b) { return 2 * a; } else { return (2 * Math.Max(a, b) - 1); } } static public void Main() { // Code int a = 4; int b = 4; // Function call Console.WriteLine(minOperations(a, b)); } } // This code is contributed by karthik. |
Javascript
// JavaScript code for the above approach // Function to count minimum operations // Required function minOperations(a, b) { if (a == b) { return 2 * a; } else { return 2 * Math.max(a, b) - 1; } } // Driver code let a = 4; let b = 4; // Function call console.log(minOperations(a, b)); |
8
Time Complexity: O(1)
Auxiliary Space: O(1)