logo

TechCodeview

Smjer na zadnjem kvadratnom bloku

S obzirom 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.

što je korisničko ime

Na primjer: Razmotrimo slučaj s R = 3 C = 3. Put koji slijedi bit će (0 0) -- (0 1) -- (0 2) -- (1 2) -- (2 2) -- (2 1) -- (2 0) -- (1 0) -- (1 1). U ovom trenutku svi su kvadrati posjećeni i okrenuti su desno. 



Primjeri:  

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

Jednostavno rješenje: Jedno jednostavno rješenje za ovaj problem je napraviti R x C matricu inicijaliziranu s nulom i preći je u spiralnom obliku i uzeti varijablu 'Dir' koja govori trenutni smjer. Kad god smo na kraju bilo kojeg retka ili stupca, skrenite desno i promijenite vrijednost 'Dir' prema vašem trenutnom smjeru. Sada slijedite zadane uvjete: 

  • Ako prelazite gornji red, vaš trenutni smjer je desno.
  • Ako ste u desnom stupcu, vaš trenutni smjer je dolje.
  • Ako prelazite donji red, tada je vaš trenutni smjer lijevo.
  • Ako prelazite po lijevom stupcu, vaš trenutni smjer je gore.

Kada dođemo do posljednjeg kvadrata samo ispišite trenutni smjer tj.; vrijednost varijable 'Dir'. 
Vremenska i prostorna složenost za ovaj problem je O(R x C) i ovo će raditi samo za male vrijednosti R C, ali ovdje su R i C preveliki tako da stvaranje R x C matrice nije moguće za prevelike vrijednosti R i C.



Učinkovit pristup: Ovaj pristup zahtijeva malo promatranja i malo rada s papirom. Ovdje moramo razmotriti sve moguće slučajeve za R i C, a zatim samo trebamo staviti IF uvjet za sve moguće slučajeve. Evo nas sa svim mogućim uvjetima: 

isječak java niza
  1. R != C i R je paran, a C neparan i R
  2. R != C i R je neparan, a C paran i R
  3. R != C i R je paran i C je paran i R
  4. R != C i R je neparan i C je neparan i R
  5. R != C i R je paran, a C neparan i R>C smjer će biti prema dolje.
  6. R != C i R je neparan, a C paran i R>C smjer će biti gore.
  7. R != C i R je paran i C je paran i R>C smjer će biti gore.
  8. R != C i R je neparan i C je neparan i R>C smjer će biti dolje.
  9. R == C i R je paran, a C je paran smjer će biti lijevo.
  10. R == C i R je neparan i C je neparan smjer će biti desno.

Ispod je implementacija gornje 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('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>

Izlaz 
Down

Vremenska složenost: O(1) 
Pomoćni prostor: O(1)



Ovaj je članak pregledao tim GeeksforGeeks.