Wednesday, November 30, 2022
HomeSoftware DevelopmentExamine if adjoining cell of Begin could be reached visiting all cells...

Examine if adjoining cell of Begin could be reached visiting all cells as soon as


Given two integers X and Y, which symbolize the variety of rows and columns respectively of a matrix, the duty is to test whether or not there exists a path, Which follows all of the beneath situations:

  • Beginning of the trail is from the cell (1, 1).
  • Ending of the trail is any cell adjoining to (1, 1).
  • You need to traverse every cell of the matrix solely as soon as.

Notice: Right here 1 primarily based indexing is used.

Examples:

Enter:  X = 2, Y = 3
Output: YES
Rationalization:

Explanation for input test case

Rationalization for enter check case

Every cell is traversed as soon as, beginning cell is (1, 1) and ending cell is (2, 1), Which is adjoining to (1, 1). Therefore, all of the situations met.

Enter: X = 1, Y = 1
Output: NO
Rationalization:  As there isn’t any adjoining cell of ( 1, 1 ) exists due to this fact, Output is NO.

Strategy: The issue could be solved primarily based on the next statement:

Statement:

Let’s take some random test-cases. 

Take a look at case 1: X = 4, Y = 4 
Output: YES
Rationalization:

Explanation for test case 1

Rationalization for check case 1

Take a look at case 2:  X=4, Y=5
Output: YES
Rationalization:

Explanation for test case 2

Rationalization for check case 2

Take a look at case 3: X = 1, Y =3 
Output: NO
Rationalization: No path is feasible that fulfill given constraints.

From all above check circumstances, We are able to conclude some situations:

  • If each X and Y are odd, Then there exists no path.
  • If (X = 1 && Y > 2) or (Y = 1 && X > 2), Then no path exists.
  • All of the circumstances besides above mentioned 2( quantity 1 and quantity 2 ) circumstances can have a path.    

Comply with the beneath steps to implement the concept:

  • Examine the situations on X and Y mentioned above.
  • If the values match any of the primary two situations then no path is feasible.
  • In any other case, there exists a path.

Beneath is the implementation of the above method.

Java

  

import java.io.*;

import java.lang.*;

import java.util.*;

  

class GFG {

  

    

    public static void essential(String args[])

    {

        lengthy X = 2, Y = 2;

  

        

        System.out.println(Is_Path_Possible(X, Y));

    }

  

    

    static String Is_Path_Possible(lengthy X, lengthy Y)

    {

        

        

        if (X % 2 != 0 && Y % 2 != 0 || X == 1 && Y > 2

            || Y == 1 && X > 2) {

  

            return "NO";

        }

        else {

            return "YES";

        }

    }

}

Time Complexity: O(1)
Auxiliary House: O(1)  

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments