Retning ved sidste firkantede blok
Givet en R x C (1 <= R C <= 1000000000) grid and initial position as top left corner and direction as east. Now we start running in forward direction and cross each square blocks of matrix. Whenever we find dead end or reach a cell that is already visited we take right because we can not cross the visited square blocks again. Tell the direction when we will be at last square block.
For eksempel: Overvej tilfældet med R = 3 C = 3. Den sti, der følges, vil være (0 0) -- (0 1) -- (0 2) -- (1 2) -- (2 2) -- (2 1) -- (2 0) -- (1 0) -- (1 1). På dette tidspunkt er alle pladser blevet besøgt og vender mod højre.
Eksempler:
Input : R = 1 C = 1 Output : Right Input : R = 2 C = 2 Output : Left Input : R = 3 C = 1 Output : Down Input : R = 3 C = 3 Output : Right
Simpel løsning: En simpel løsning på dette problem er at gøre den R x C-matrix initialiseret med nul og krydse den i spiralform og tage en variabel 'Dir', der fortæller den aktuelle retning. Når vi er i slutningen af en række og kolonne, skal du tage til højre og ændre værdien af 'Dir' i henhold til din aktuelle retning. Følg nu de givne betingelser:
- Hvis du krydser den øverste række, er din nuværende retning højre.
- Hvis du er højre kolonne, så er din nuværende retning Ned.
- Hvis du krydser nederste række, er din aktuelle retning Venstre.
- Hvis du krydser venstre kolonne, er din aktuelle retning op.
Når vi når til den sidste firkant udskriver du bare den aktuelle retning dvs. værdien af 'Dir'-variablen.
Tids- og rumkompleksiteten for dette problem er O(R x C), og dette vil kun fungere for små værdier af RC, men her er R og C for store, så det er ikke muligt at oprette R x C-matrix for for store værdier af R og C.
Effektiv tilgang: Denne tilgang kræver lidt observation og noget pennepapirarbejde. Her skal vi overveje alle mulige tilfælde for R og C, så skal vi bare sætte IF-betingelse for alle mulige tilfælde. Her er vi med alle mulige betingelser:
- R != C og R er lige og C er ulige og R
- R != C og R er ulige og C er lige og R
- R != C og R er lige og C er lige og R
- R != C og R er ulige og C er ulige og R
- R != C og R er lige og C er ulige og R>C retning vil være Ned.
- R != C og R er ulige og C er lige og R>C retning vil være op.
- R != C og R er lige og C er lige og R>C retning vil være op.
- R != C og R er ulige og C er ulige og R>C retning vil være Ned.
- R == C og R er lige og C er lige retning vil være venstre.
- R == C og R er ulige og C er ulige retning vil være højre.
- R != C og R er ulige og C er lige og R
Nedenfor er implementering af ovenstående idé.
C++ // C++ program to tell the Current direction in // R x C grid #include using namespace std ; typedef long long int ll ; // Function which tells the Current direction void direction ( ll R ll C ) { if ( R != C && R % 2 == 0 && C % 2 != 0 && R < C ) { cout < < 'Left' < < endl ; return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R > C ) { cout < < 'Up' < < endl ; return ; } if ( R == C && R % 2 != 0 && C % 2 != 0 ) { cout < < 'Right' < < endl ; return ; } if ( R == C && R % 2 == 0 && C % 2 == 0 ) { cout < < 'Left' < < endl ; return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R < C ) { cout < < 'Right' < < endl ; return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R > C ) { cout < < 'Down' < < endl ; return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R < C ) { cout < < 'Left' < < endl ; return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R > C ) { cout < < 'Up' < < endl ; return ; } if ( R != C && R % 2 == 0 && C % 2 != 0 && R > C ) { cout < < 'Down' < < endl ; return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R < C ) { cout < < 'Right' < < endl ; return ; } } // Driver program to test the Cases int main () { ll R = 3 C = 1 ; direction ( R C ); return 0 ; }
C // C program to tell the Current direction in // R x C grid #include typedef long long int ll ; // Function which tells the Current direction void direction ( ll R ll C ) { if ( R != C && R % 2 == 0 && C % 2 != 0 && R < C ) { printf ( 'Left n ' ); return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R > C ) { printf ( 'Up n ' ); return ; } if ( R == C && R % 2 != 0 && C % 2 != 0 ) { printf ( 'Right n ' ); return ; } if ( R == C && R % 2 == 0 && C % 2 == 0 ) { printf ( 'Left n ' ); return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R < C ) { printf ( 'Right n ' ); return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R > C ) { printf ( 'Down n ' ); return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R < C ) { printf ( 'Left n ' ); return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R > C ) { printf ( 'Up n ' );; return ; } if ( R != C && R % 2 == 0 && C % 2 != 0 && R > C ) { printf ( 'Down n ' ); return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R < C ) { printf ( 'Right n ' ); return ; } } // Driver program to test the Cases int main () { ll R = 3 C = 1 ; direction ( R C ); return 0 ; } // This code is contributed by kothavvsaakash.
Java // Java program to tell the Current direction in // R x C grid import java.io.* ; class GFG { // Function which tells the Current direction static void direction ( int R int C ) { if ( R != C && R % 2 == 0 && C % 2 != 0 && R < C ) { System . out . println ( 'Left' ); return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R > C ) { System . out . println ( 'Up' ); return ; } if ( R == C && R % 2 != 0 && C % 2 != 0 ) { System . out . println ( 'Right' ); return ; } if ( R == C && R % 2 == 0 && C % 2 == 0 ) { System . out . println ( 'Left' ); return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R < C ) { System . out . println ( 'Right' ); return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R > C ) { System . out . println ( 'Down' ); return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R < C ) { System . out . println ( 'Left' ); return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R > C ) { System . out . println ( 'Up' ); return ; } if ( R != C && R % 2 == 0 && C % 2 != 0 && R > C ) { System . out . println ( 'Down' ); return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R < C ) { System . out . println ( 'Right' ); return ; } } // Driver code public static void main ( String [] args ) { int R = 3 C = 1 ; direction ( R C ); } } // This code is contributed by KRV.
Python3 # Python3 program to tell the Current # direction in R x C grid # Function which tells the Current direction def direction ( R C ): if ( R != C and R % 2 == 0 and C % 2 != 0 and R < C ): print ( 'Left' ) return if ( R != C and R % 2 == 0 and C % 2 == 0 and R > C ): print ( 'Up' ) return if R == C and R % 2 != 0 and C % 2 != 0 : print ( 'Right' ) return if R == C and R % 2 == 0 and C % 2 == 0 : print ( 'Left' ) return if ( R != C and R % 2 != 0 and C % 2 != 0 and R < C ): print ( 'Right' ) return if ( R != C and R % 2 != 0 and C % 2 != 0 and R > C ): print ( 'Down' ) return if ( R != C and R % 2 == 0 and C % 2 != 0 and R < C ): print ( 'Left' ) return if ( R != C and R % 2 == 0 and C % 2 == 0 and R > C ): print ( 'Up' ) return if ( R != C and R % 2 != 0 and C % 2 != 0 and R > C ): print ( 'Down' ) return if ( R != C and R % 2 != 0 and C % 2 != 0 and R < C ): print ( 'Right' ) return # Driver code R = 3 ; C = 1 direction ( R C ) # This code is contributed by Shrikant13
C# // C# program to tell the Current // direction in R x C grid using System ; class GFG { // Function which tells // the Current direction static void direction ( int R int C ) { if ( R != C && R % 2 == 0 && C % 2 != 0 && R < C ) { Console . WriteLine ( 'Left' ); return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R > C ) { Console . WriteLine ( 'Up' ); return ; } if ( R == C && R % 2 != 0 && C % 2 != 0 ) { Console . WriteLine ( 'Right' ); return ; } if ( R == C && R % 2 == 0 && C % 2 == 0 ) { Console . WriteLine ( 'Left' ); return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R < C ) { Console . WriteLine ( 'Right' ); return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R > C ) { Console . WriteLine ( 'Down' ); return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R < C ) { Console . WriteLine ( 'Left' ); return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R > C ) { Console . WriteLine ( 'Up' ); return ; } if ( R != C && R % 2 == 0 && C % 2 != 0 && R > C ) { Console . WriteLine ( 'Down' ); return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R < C ) { Console . WriteLine ( 'Right' ); return ; } } // Driver code static public void Main () { int R = 3 C = 1 ; direction ( R C ); } } // This code is contributed by m_kit
PHP // PHP program to tell the Current // direction in R x C grid // Function which tells // the Current direction function direction ( $R $C ) { if ( $R != $C && $R % 2 == 0 && $C % 2 != 0 && $R < $C ) { echo 'Left' ' n ' ; return ; } if ( $R != $C && $R % 2 != 0 && $C % 2 == 0 && $R > $C ) { echo 'Up' ' n ' ; return ; } if ( $R == $C && $R % 2 != 0 && $C % 2 != 0 ) { echo 'Right' ' n ' ; return ; } if ( $R == $C && $R % 2 == 0 && $C % 2 == 0 ) { echo 'Left' ' n ' ; return ; } if ( $R != $C && $R % 2 != 0 && $C % 2 != 0 && $R < $C ) { echo 'Right' ' n ' ; return ; } if ( $R != $C && $R % 2 != 0 && $C % 2 != 0 && $R > $C ) { echo 'Down' ' n ' ; return ; } if ( $R != $C && $R % 2 == 0 && $C % 2 == 0 && $R < $C ) { echo 'Left' ' n ' ; return ; } if ( $R != $C && $R % 2 == 0 && $C % 2 == 0 && $R > $C ) { echo 'Up' ' n ' ; return ; } if ( $R != $C && $R % 2 == 0 && $C % 2 != 0 && $R > $C ) { echo 'Down' ' n ' ; return ; } if ( $R != $C && $R % 2 != 0 && $C % 2 == 0 && $R < $C ) { echo 'Right' ' n ' ; return ; } } // Driver Code $R = 3 ; $C = 1 ; direction ( $R $C ); // This code is contributed by aj_36 ?>
JavaScript < script > // Javascript program to tell the Current // direction in R x C grid // Function which tells // the Current direction function direction ( R C ) { if ( R != C && R % 2 == 0 && C % 2 != 0 && R < C ) { document . write ( 'Left' ); return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R > C ) { document . write ( 'Up' ); return ; } if ( R == C && R % 2 != 0 && C % 2 != 0 ) { document . write ( 'Right' ); return ; } if ( R == C && R % 2 == 0 && C % 2 == 0 ) { document . write ( 'Left' ); return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R < C ) { document . write ( 'Right' ); return ; } if ( R != C && R % 2 != 0 && C % 2 != 0 && R > C ) { document . write ( 'Down' ); return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R < C ) { document . write ( 'Left' ); return ; } if ( R != C && R % 2 == 0 && C % 2 == 0 && R > C ) { document . write ( 'Up' ); return ; } if ( R != C && R % 2 == 0 && C % 2 != 0 && R > C ) { document . write ( 'Down' ); return ; } if ( R != C && R % 2 != 0 && C % 2 == 0 && R < C ) { document . write ( 'Right' ); return ; } } let R = 3 C = 1 ; direction ( R C ); < /script>
Produktion
Down
Tidskompleksitet: O(1)
Hjælpeplads: O(1)
Denne artikel er gennemgået af team GeeksforGeeks.
