כיוון בבלוק המרובע האחרון

נתון 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.

לדוגמא: שקול את המקרה עם R = 3 C = 3. הנתיב אחריו יהיה (0 0) -- (0 1) -- (0 2) -- (1 2) -- (2 2) -- (2 1) -- (2 0) -- (1 0) -- (1 1). בשלב זה כל הכיכרות ביקרו ופונות ימינה.

דוגמאות:

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

פתרון פשוט: פתרון פשוט אחד לבעיה זו הוא להפוך אותה למטריצת R x C לאתחל באפס ולחצות אותה בצורה ספירלית ולקחת משתנה 'Dir' שמספר את הכיוון הנוכחי. בכל פעם שאנו נמצאים בסוף שורה ועמודה כלשהי, קח ימינה ושנה את הערך של 'Dir' בהתאם לכיוון הנוכחי שלך. כעת פעל לפי התנאים המפורטים:

אם אתה חוצה את השורה העליונה אז הכיוון הנוכחי שלך הוא נכון.
אם אתה בעמודה הימנית, הכיוון הנוכחי שלך הוא למטה.
אם אתה חוצה את השורה התחתונה, הכיוון הנוכחי שלך הוא שמאלה.
אם אתה חוצה את העמודה השמאלית, הכיוון הנוכחי שלך הוא למעלה.

כשאנחנו מגיעים לריבוע האחרון פשוט מדפיסים כיוון נוכחי כלומר; הערך של משתנה 'Dir'.
מורכבות הזמן והמרחב עבור בעיה זו היא O(R x C) וזה יעבוד רק עבור ערכים קטנים של RC אך כאן R ו-C גדולים מדי ולכן יצירת מטריצת R x C אינה אפשרית עבור ערכים גדולים מדי של R ו-C.

גישה יעילה: גישה זו דורשת התבוננות מועטה וקצת עבודת נייר בעט. כאן אנחנו צריכים לשקול את כל המקרים האפשריים עבור R ו-C ואז אנחנו רק צריכים לשים תנאי IF עבור כל המקרים האפשריים. הנה אנחנו עם כל התנאים האפשריים:

R != C ו-R זוגי ו-C אי זוגי ו-R
R != C ו-R הוא אי זוגי ו-C הוא זוגי ו-R
R != C ו-R זוגי ו-C זוגי ו-R
R != C ו-R הוא אי-זוגי ו-C הוא אי-זוגי ו-R
R != C ו-R זוגי ו-C אי זוגי וכיוון R>C יהיה למטה.
R != C ו-R הוא אי זוגי ו-C הוא זוגי וכיוון R>C יהיה למעלה.
R != C ו-R זוגי ו-C זוגי וכיוון R>C יהיה למעלה.
R != C ו-R הוא אי זוגי ו-C הוא אי זוגי וכיוון R>C יהיה למטה.
R == C ו-R הוא זוגי ו-C הוא זוגי כיוון יהיה שמאלה.
R == C ו-R הוא אי זוגי ו-C הוא אי זוגי הכיוון יהיה נכון.

להלן יישום הרעיון לעיל.

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 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# 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>

תְפוּקָה

Down

מורכבות זמן: O(1)
מרחב עזר: O(1)

מאמר זה נבדק על ידי צוות GeeksforGeeks.