logo

TechCodeview

Směr na poslední čtvercový blok

Vzhledem k 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.

Například: Uvažujme případ s R = 3 C = 3. Následovaná cesta bude (0 0) -- (0 1) -- (0 2) -- (1 2) -- (2 2) -- (2 1) -- (2 0) -- (1 0) -- (1 1). V tomto okamžiku byla všechna náměstí navštívena a je otočena doprava. 



Pří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é řešení: Jedním jednoduchým řešením tohoto problému je vytvořit matici R x C inicializovanou nulou a procházet ji ve tvaru spirály a vzít proměnnou 'Dir', která říká aktuální směr. Kdykoli jsme na konci libovolného řádku a sloupce, jděte doprava a změňte hodnotu 'Dir' podle vašeho aktuálního směru. Nyní dodržujte dané podmínky: 

  • Pokud procházíte horní řadou, váš aktuální směr je vpravo.
  • Pokud jste ve sloupci vpravo, váš aktuální směr je Dolů.
  • Pokud procházíte spodní řadou, váš aktuální směr je doleva.
  • Pokud procházíte levým sloupcem, váš aktuální směr je Nahoru.

Když se dostaneme na poslední čtverec, stačí vytisknout aktuální směr, tj. hodnota proměnné 'Dir'. 
Časová a prostorová složitost pro tento problém je O(R x C) a to bude fungovat pouze pro malé hodnoty R C, ale zde jsou R a C příliš velké, takže vytvoření matice R x C není možné pro příliš velké hodnoty R a C.



Efektivní přístup: Tento přístup vyžaduje malé pozorování a trochu práce s papírem. Zde musíme vzít v úvahu všechny možné případy pro R a C, pak stačí dát podmínku IF pro všechny možné případy. Zde jsme se všemi možnými podmínkami: 

  1. R = C a R je sudé a C je liché a R
  2. R = C a R je liché a C je sudé a R
  3. R = C a R je sudé a C je sudé a R
  4. R = C a R je liché a C je liché a R
  5. R != C a R je sudé a C je liché a směr R>C bude dolů.
  6. R != C a R je liché a C je sudé a směr R>C bude nahoru.
  7. R != C a R je sudé a C je sudé a směr R>C bude nahoru.
  8. R != C a R je liché a C je liché a směr R>C bude dolů.
  9. R == C a R je sudé a C je sudé směr bude vlevo.
  10. R == C a R je liché a C je liché směr bude pravý.

Níže je implementace výše uvedené myšlenky. 

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á složitost: O(1) 
Pomocný prostor: O(1)



Tento článek je zkontrolován týmem GeeksforGeeks.