Richting bij laatste vierkant blok
Gegeven een 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.
Bijvoorbeeld : Beschouw het geval met R = 3 C = 3. Het gevolgde pad is (0 0) -- (0 1) -- (0 2) -- (1 2) -- (2 2) -- (2 1) -- (2 0) -- (1 0) -- (1 1). Op dit punt zijn alle pleinen bezocht en zijn ze naar rechts gericht.
Voorbeelden:
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
Eenvoudige oplossing: Een eenvoudige oplossing voor dit probleem is om de R x C-matrix te initialiseren met nul en deze in spiraalvorm te doorlopen en een variabele 'Dir' te nemen die de huidige richting aangeeft. Wanneer we aan het einde van een rij of kolom zijn, gaat u naar rechts en wijzigt u de waarde van 'Dir' volgens uw huidige richting. Volg nu de gegeven voorwaarden:
- Als u de bovenste rij doorkruist, is uw huidige richting Rechts.
- Als u in de rechterkolom staat, is uw huidige richting Omlaag.
- Als u de onderste rij doorkruist, is uw huidige richting links.
- Als u de linkerkolom doorkruist, is uw huidige richting Omhoog.
Wanneer we het laatste vierkant bereiken, drukt u gewoon de huidige richting af, d.w.z.; waarde van de variabele 'Dir'.
De tijd- en ruimtecomplexiteit voor dit probleem is O(R x C) en dit werkt alleen voor kleine waarden van R C, maar hier zijn R en C te groot, dus het creëren van een R x C-matrix is niet mogelijk voor te grote waarden van R en C.
Efficiënte aanpak: Deze aanpak vereist weinig observatie en wat penpapierwerk. Hier moeten we alle mogelijke gevallen voor R en C overwegen, en dan hoeven we alleen maar de IF-voorwaarde voor alle mogelijke gevallen te plaatsen. Hier zijn we met alle mogelijke voorwaarden:
- R != C en R is even en C is oneven en R
- R != C en R is oneven en C is even en R
- R != C en R is even en C is even en R
- R != C en R is oneven en C is oneven en R
- R != C en R is even en C is oneven en de R>C-richting is omlaag.
- R != C en R is oneven en C is even en de R>C-richting is omhoog.
- R != C en R is even en C is even en de R>C-richting is omhoog.
- R != C en R is oneven en C is oneven en de R>C-richting is omlaag.
- R == C en R is even en C is even richting links.
- R == C en R is oneven en C is oneven richting zal goed zijn.
- R != C en R is oneven en C is even en R
Hieronder vindt u de implementatie van het bovenstaande idee.
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>
Uitvoer
Down
Tijdcomplexiteit: O(1)
Hulpruimte: O(1)
Dit artikel is beoordeeld door team GeeksforGeeks.
