ישנו מבוך הנתון במערך דו-ממדי של מספרים שלמים. כל תא במבוך יכול להיות ניתן למעבר, קיר (חסום) או דרקון. מכל תא ניתן לנוע ימינה, שמאלה, למעלה או למטה, אך לא באלכסון, ולא ניתן לעבור דרך קיר.
יש למצוא מסלול שמתחיל בתא [0][0] ומסתיים בתא שבפינה הימנית התחתונה של המערך. העובר דרך מספר מינימלי של דרקונים. יש להחזיר את מספר הדרקונים במסלול האופטימלי שנמצא.
אם אין מסלול בכלל, יוחזר המספר השלם הגדול ביותר האפשרי - Integer.MAX_VALUE.
קיר מסומן על־ידי הערך 0, תא פתוח על־ידי הערך 1 ודרקון על־ידי הערך 3.
דוגמה:
במבוך הנתון יש מספר מסלולים תקפים המתחילים בתא [0][0] ומסתיימים בתא שבפינה הימנית התחתונה של המערך. המטרה היא למצוא מסלול שעובר דרך מספר מינימלי של דרקונים. אם המסלול האופטימלי עובר דרך דרקון אחד בלבד, השיטה צריכה להחזיר 1. אם המסלול האופטימלי עובר דרך 4 דרקונים, השיטה צריכה להחזיר 4. במידה שאין מסלול אפשרי מהתחלה למטרה, יוחזר Integer.MAX_VALUE.
דוגמה 1
| 0 | 1 | 2 | 3 | |
| 0 | 1 | 0 | 3 | 3 |
| 1 | 3 | 0 | 1 | 1 |
| 2 | 3 | 0 | 0 | 0 |
| 3 | 0 | 3 | 3 | 1 |
דוגמה 2
| 0 | 1 | 2 | 3 | |
| 0 | 1 | 1 | 3 | 3 |
| 1 | 3 | 0 | 1 | 1 |
| 2 | 3 | 0 | 0 | 0 |
| 3 | 1 | 3 | 3 | 1 |
תשובה: 4
דוגמה 3
| 0 | 1 | 2 | 3 | |
| 0 | 1 | 1 | 3 | 3 |
| 1 | 3 | 0 | 1 | 1 |
| 2 | 3 | 0 | 0 | 1 |
| 3 | 1 | 3 | 3 | 1 |
תשובה: 1
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
ניתן לשנות את המערך בזמן ריצת השיטה, אולם בסופה הוא צריך לחזור למצבו ההתחלתי.
המערך מלא בנתונים חוקיים.
maze = [[1, 0, 3, 3], [3, 0, 1, 1], [3, 0, 0, 0], [0, 3, 3, 1]]
Integer.MAX_VALUE
הסבר: אין מסלול אפשרי למטרה, לכן מוחזר Integer.MAX_VALUE
maze = [[1, 1, 3, 3], [3, 0, 1, 1], [3, 0, 0, 0], [1, 3, 3, 1]]
4
הסבר: המסלול האופטימלי עובר דרך 4 דרקונים
maze = [[1, 1, 3, 3], [3, 0, 1, 1], [3, 0, 0, 1], [1, 3, 3, 1]]
1
הסבר: המסלול האופטיטמלי עובר דרך דרקון אחד
maze = [[1, 1], [1, 1]]
0
הסבר: מבוך פשוט ללא דרקונים, מסלול ללא דרקונים
maze = [[3, 3], [3, 3]]
3
הסבר: כל התאים הם דרקונים, ועוברים דרך 3 דרקונים
maze = [[1, 3, 1], [1, 1, 1], [3, 1, 1]]
0
הסבר: ישנו מסלול ללא דרקונים דרך התאים הפתוחים
maze = [[1, 0, 0], [0, 3, 1], [0, 0, 1]]
Integer.MAX_VALUE
הסבר: אין מסלול אפשרי כיוון שכל התאים חסומים
maze = [[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1]]
Integer.MAX_VALUE
הסבר: אין מסלול אפשרי כיוון שכל התאים חסומים
קלט:
maze = [[1, 0, 3, 3], [3, 0, 1, 1], [3, 0, 0, 0], [0, 3, 3, 1]]
הפלט המבוקש:
Integer.MAX_VALUE