logo

TechCodeview

Kryptis paskutiniame kvadratiniame bloke

Duota 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.

Pavyzdžiui: Apsvarstykite atvejį, kai R = 3 C = 3. Kelias bus (0 0) -- (0 1) -- (0 2) -- (1 2) -- (2 2) -- (2 1) -- (2 0) -- (1 0) -- (1 1). Šiuo metu visos aikštės buvo aplankytos ir yra nukreiptos į dešinę. 



Pavyzdžiai:  

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

Paprastas sprendimas: Vienas iš paprastų šios problemos sprendimų yra padaryti ją R x C matricą inicijuotą nuliu ir spiraliniu pavidalu paimti kintamąjį „Dir“, kuris nurodo srovės kryptį. Kai esame bet kurios eilutės ir stulpelio pabaigoje, pasukite dešinėn ir pakeiskite „Dir“ reikšmę pagal savo dabartinę kryptį. Dabar laikykitės pateiktų sąlygų: 

  • Jei važiuojate viršutine eilute, jūsų dabartinė kryptis yra teisinga.
  • Jei esate dešiniajame stulpelyje, dabartinė jūsų kryptis yra žemyn.
  • Jei važiuojate apatine eilute, jūsų dabartinė kryptis yra kairė.
  • Jei važiuojate kairiuoju stulpeliu, dabartinė jūsų kryptis yra aukštyn.

Kai pasiekiame paskutinį kvadratą, tiesiog atspausdinkite srovės kryptį, ty; kintamojo „Dir“ reikšmė. 
Šios problemos laiko ir erdvės sudėtingumas yra O(R x C) ir tai veiks tik esant mažoms R C reikšmėms, tačiau čia R ir C yra per dideli, todėl sukurti R x C matricą neįmanoma esant per didelėms R ir C reikšmėms.



Efektyvus požiūris: Šis metodas reikalauja mažai stebėjimo ir šiek tiek darbo rašikliu. Čia turime apsvarstyti visus galimus R ir C atvejus, tada tereikia pateikti IF sąlygą visiems galimiems atvejams. Štai su visomis įmanomomis sąlygomis: 

  1. R != C ir R yra lyginis, o C yra nelyginis ir R
  2. R = C ir R yra nelyginis, o C yra lyginis ir R
  3. R != C ir R yra lyginis, o C yra lyginis ir R
  4. R = C ir R yra nelyginis, o C yra nelyginis ir R
  5. R != C ir R yra lyginis, o C yra nelyginis, o R>C kryptis bus žemyn.
  6. R != C ir R yra nelyginis, o C lyginis, o R>C kryptis bus aukštyn.
  7. R != C ir R yra lyginės, o C yra lyginės ir R>C kryptis bus aukštyn.
  8. R != C ir R yra nelyginis, o C yra nelyginis, o R>C kryptis bus žemyn.
  9. R == C ir R yra lygūs, o C yra lyginė kryptis bus kairė.
  10. R == C ir R yra nelyginis, o C yra nelyginis kryptis bus teisinga.

Žemiau yra aukščiau pateiktos idėjos įgyvendinimas. 

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('Leftn');  return;  }  if (R != C && R % 2 != 0 && C % 2 == 0 && R > C) {  printf('Upn');  return;  }  if (R == C && R % 2 != 0 && C % 2 != 0) {  printf('Rightn');  return;  }  if (R == C && R % 2 == 0 && C % 2 == 0) {  printf('Leftn');  return;  }  if (R != C && R % 2 != 0 && C % 2 != 0 && R < C) {  printf('Rightn');  return;  }  if (R != C && R % 2 != 0 && C % 2 != 0 && R > C) {  printf('Downn');  return;  }  if (R != C && R % 2 == 0 && C % 2 == 0 && R < C) {  printf('Leftn');  return;  }  if (R != C && R % 2 == 0 && C % 2 == 0 && R > C) {  printf('Upn');;  return;  }  if (R != C && R % 2 == 0 && C % 2 != 0 && R > C) {  printf('Downn');  return;  }  if (R != C && R % 2 != 0 && C % 2 == 0 && R < C) {  printf('Rightn');  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>

Išvestis 
Down

Laiko sudėtingumas: O(1) 
Pagalbinė erdvė: O(1)



Šį straipsnį peržiūri komanda GeeksforGeeks.