Son kare bloktaki yön
Verilen bir 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.
Örneğin : R = 3 C = 3 durumunu düşünün. İzlenen yol (0 0) -- (0 1) -- (0 2) -- (1 2) -- (2 2) -- (2 1) -- (2 0) -- (1 0) -- (1 1) olacaktır. Bu noktada tüm meydanlar gezilmiş olup sağa dönülmektedir.
Örnekler:
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
Basit Çözüm: Bu problemin basit bir çözümü, R x C matrisini sıfırla başlatmak ve onu spiral biçimde hareket ettirmek ve mevcut yönü söyleyen bir 'Dir' değişkeni almaktır. Herhangi bir satırın veya sütunun sonuna geldiğimizde Sağa dönün ve 'Dir'in değerini mevcut yönünüze göre değiştirin. Şimdi verilen koşulları izleyin:
- Üst sırayı geçiyorsanız mevcut yönünüz Sağdır.
- Sağ sütundaysanız mevcut yönünüz Aşağıdır.
- Alt sırayı geçiyorsanız mevcut yönünüz Soldur.
- Sol sütunda ilerliyorsanız mevcut yönünüz Yukarıdır.
Son kareye ulaştığımızda sadece geçerli yönü yazdırın; 'Dir' değişkeninin değeri.
Bu problem için zaman ve uzay karmaşıklığı O(R x C)'dir ve bu yalnızca R C'nin küçük değerleri için işe yarayacaktır ancak burada R ve C çok büyüktür, dolayısıyla çok büyük R ve C değerleri için R x C matrisi oluşturmak mümkün değildir.
Verimli Yaklaşım: Bu yaklaşım çok az gözlem ve biraz kalem çalışması gerektirir. Burada R ve C için tüm olası durumları dikkate almamız gerekiyor, ardından tüm olası durumlar için sadece IF koşulunu koymamız gerekiyor. İşte tüm olası koşullarla birlikteyiz:
- R != C ve R çift ve C tek ve R
- R != C ve R tek ve C çift ve R
- R != C ve R çifttir ve C çifttir ve R
- R != C ve R tektir ve C tektir ve R
- R != C ve R çift ve C tektir ve R>C yönü Aşağı olacaktır.
- R != C ve R tek, C çift ve R>C yönü Yukarı olacaktır.
- R != C ve R çift ve C çifttir ve R>C yönü Yukarı olacaktır.
- R != C ve R tek ve C tektir ve R>C yönü Aşağı olacaktır.
- R == C ve R çift ve C çift yön Sol olacaktır.
- R == C ve R tek ve C tek yön Sağa olacaktır.
- R != C ve R tek ve C çift ve R
Aşağıda yukarıdaki fikrin uygulanması yer almaktadır.
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>
Çıkış
Down
Zaman Karmaşıklığı : O(1)
Yardımcı Alan : O(1)
Bu makale GeeksforGeeks ekibi tarafından incelenmiştir.
