Smer pri zadnjem kvadratnem bloku
Glede na 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.
Na primer: Razmislite o primeru z R = 3 C = 3. Pot, ki ji sledite, bo (0 0) -- (0 1) -- (0 2) -- (1 2) -- (2 2) -- (2 1) -- (2 0) -- (1 0) -- (1 1). Na tej točki so vsi kvadrati obiskani in je obrnjena desno.
Primeri:
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
Preprosta rešitev: Ena preprosta rešitev za to težavo je, da se matrika R x C inicializira z ničlo in jo prečka v spiralni obliki ter vzame spremenljivko 'Dir', ki pove trenutno smer. Kadarkoli smo na koncu katere koli vrstice ali stolpca, zavijte desno in spremenite vrednost 'Dir' glede na vašo trenutno smer. Zdaj upoštevajte dane pogoje:
- Če prečkate zgornjo vrstico, je vaša trenutna smer desno.
- Če ste v desnem stolpcu, je vaša trenutna smer navzdol.
- Če prečkate spodnjo vrstico, je vaša trenutna smer levo.
- Če prečkate levi stolpec, je vaša trenutna smer gor.
Ko pridemo do zadnjega polja, natisnemo trenutno smer, tj. vrednost spremenljivke 'Dir'.
Časovna in prostorska zapletenost za ta problem je O(R x C) in to bo delovalo samo za majhne vrednosti R C, vendar sta R in C prevelika, zato ustvarjanje matrike R x C ni mogoče za prevelike vrednosti R in C.
Učinkovit pristop: Ta pristop zahteva malo opazovanja in nekaj dela s peresom. Tu moramo upoštevati vse možne primere za R in C, nato pa moramo le postaviti pogoj IF za vse možne primere. Tukaj smo z vsemi možnimi pogoji:
- R != C in R je sodo in C je liho in R
- R != C in R je liho in C je sodo in R
- R != C in R je sodo in C je sodo in R
- R != C in R je liho in C je liho in R
- R != C in R je sodo in C je liho in smer R>C bo navzdol.
- R != C in R je liho in C je sodo in smer R>C bo navzgor.
- R != C in R je sodo in C je sodo in smer R>C bo navzgor.
- R != C in R je liho in C je liho in smer R>C bo navzdol.
- R == C in R je sodo in C je soda smer bo levo.
- R == C in R je liho in C je liha smer bo Desna.
- R != C in R je liho in C je sodo in R
Spodaj je izvedba zgornje ideje.
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>
Izhod
Down
Časovna zahtevnost: O(1)
Pomožni prostor: O(1)
Ta članek je pregledala ekipa GeeksforGeeks.
