המספר המינימלי בין המקסימומים

נתון מערך דו-ממדי ריבועי mat המכיל מספרים שלמים. נסמן את מספר השורות והעמודות במערך ב-n. המספרים ב-mat הם חיוביים ממש בלבד (ללא אפסים).

המסלולים בהם נעבור במערך מתחילים תמיד בתא הראשון (0,0) ועד לתא האחרון שהוא (n-1, n-1). כאשר אפשר לעבור מתא (i,j) לכל ארבעת שכניו מימין, משמאל, למעלה ולמטה, אבל לא באלכסון.

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

דוגמאות:

• נתונים המערכים הבאים:

• אם המערכים הם:

אז במערך C יוחזר 10, שהוא המקסימום במסלול המיטבי, והוא המינימלי מבין כל ערכי המקסימום של כל המסלולים האחרים.
אבל אם נחליף את התאים [1][3] שבו יש 16 ואת [1][2] שבו יש 7, (זה המערך D), המספר שיוחזר יהיה 12, שהוא המקסימום במסלול המסומן. שימו לב ש- 12 הוא המקסימום גם במסלול הזה:
[0][0] → [0][1] → [1][1] → [2][1] → [2][2] → [3][2] → [3][3]

אז במערך C יוחזר 21, שהוא המינימלי מבין כל ערכי המקסימום של כל המסלולים האחרים. שימו לב ל-21 הוא המקסימום בעוד כמה מסלולים. לדוגמא:

1. [0][0] → [1][0] → [2][0] → [3][0] → [3][1] → [3][2] → [3][3] → [3][4] → [4][4]
2. [0][0] → [1][0] → [2][0] → [2][1] → [2][2] → [3][2] → [3][1] → [3][0] → [4][0] → [4][4]

אבל אם נחליף את התאים 2, 14, 22 במערך (זה המערך D), המספר שיוחזר יהיה 15, שהוא המקסימום במסלול המסומן.

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

mat = 
[[1,2],
 [3,4]]

4

mat = 
[[1,3],
 [4,2]]

3

mat = 
[[4, 5, 8, 2],
 [3, 12, 7, 16],
 [13, 1, 10, 14],
 [15, 11, 9, 6]]

10

mat = 
[[4, 5, 8, 2],
 [3, 12, 16, 7],
 [13, 1, 10, 14],
 [15, 11, 9, 6]]

12

mat = [[1]]

1

mat = 
[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]

9

mat = 
[[4, 1, 9, 3, 25],
 [24, 23, 2, 21, 5],
 [13, 12, 15, 16, 22],
 [17, 11, 18, 19, 20],
 [10, 14, 8, 7, 6]]

15

mat = 
[[4, 1, 9, 3, 25],
 [24, 23, 22, 21, 5],
 [13, 12, 15, 16, 14],
 [17, 11, 18, 19, 20],
 [10, 2, 8, 7, 6]]

21