logo

TechCodeview

Smer na posledný štvorcový blok

Vzhľadom 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.

Napríklad: Uvažujme prípad s R = 3 C = 3. Nasledovaná cesta bude (0 0) -- (0 1) -- (0 2) -- (1 2) -- (2 2) -- (2 1) -- (2 0) -- (1 0) -- (1 1). V tomto bode boli navštívené všetky námestia a je otočený doprava. 



Príklady:  

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

Jednoduché riešenie: Jedným jednoduchým riešením tohto problému je vytvoriť maticu R x C inicializovanú nulou a prechádzať ju v špirálovom tvare a vziať premennú 'Dir', ktorá hovorí o aktuálnom smere. Kedykoľvek sme na konci akéhokoľvek riadku a stĺpca, choďte doprava a zmeňte hodnotu 'Dir' podľa vášho aktuálneho smeru. Teraz postupujte podľa uvedených podmienok: 

  • Ak prechádzate horným riadkom, váš aktuálny smer je Správny.
  • Ak ste v pravom stĺpci, váš aktuálny smer je dole.
  • Ak prechádzate spodným riadkom, váš aktuálny smer je Doľava.
  • Ak prechádzate ľavým stĺpcom, váš aktuálny smer je Hore.

Keď sa dostaneme na posledný štvorec, stačí vytlačiť aktuálny smer, t.j. hodnotu premennej 'Dir'. 
Časová a priestorová zložitosť pre tento problém je O(R x C) a to bude fungovať len pre malé hodnoty R C, ale tu sú R a C príliš veľké, takže vytvorenie matice R x C nie je možné pre príliš veľké hodnoty R a C.



Efektívny prístup: Tento prístup vyžaduje malé pozorovanie a trochu práce s perom. Tu musíme zvážiť všetky možné prípady pre R a C, potom stačí zadať podmienku IF pre všetky možné prípady. Tu sú všetky možné podmienky: 

  1. R = C a R je párne a C je nepárne a R
  2. R = C a R je nepárne a C je párne a R
  3. R = C a R je párne a C je párne a R
  4. R = C a R je nepárne a C je nepárne a R
  5. R != C a R je párne a C je nepárne a smer R>C bude dole.
  6. R != C a R je nepárne a C je párne a smer R>C bude hore.
  7. R != C a R je párne a C je párne a smer R>C bude hore.
  8. R != C a R je nepárne a C je nepárne a smer R>C bude dole.
  9. R == C a R je párne a C je párne smer bude doľava.
  10. R == C a R je nepárne a C je nepárne smer bude pravý.

Nižšie je uvedená implementácia vyššie uvedenej myšlienky. 

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>

Výstup 
Down

Časová zložitosť: O(1) 
Pomocný priestor: O(1)



Tento článok je skontrolovaný tímom GeeksforGeeks.