שלושה חברים

נתונה מטריצה (מערך דו-ממדי) matrix ריבועית (מספר השורות שווה למספר העמודות) מלאה במספרים 0 ו-1 בלבד. 
המטריצה מתארת את ההיכרויות בקבוצה של אנשים בדרך הבאה:

  • לכל אדם בקבוצה יש מספר.
  • אם אדם שמספרו i והאדם שמספרו j מכירים זה את זה, אזי במטריצה יש 1 במקומות [i][j] ו-[j][i]. אם הם לא מכירים זה את זה, אזי במטריצה יש 0 במקומות [i][j] ו-[j][i].
  • המטריצה היא סימטרית ביחס לאלכסון הראשי, כלומר לא ייתכן שאדם אחד מכיר אדם שני, אך האדם השני לא מכיר את האדם הראשון.
  • במקומות [i][i] במטריצה נמצא הערך 0.


יש למצוא בתוך מטריצת היכרויות שכזאת, מעגלי היכרויות של שלושה אנשים: אדם שמספרו i שמכיר אדם שמספרו j ואדם שמספרו k וגם האנשים j ו-k מכירים זה את זה.

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

אילוצים:
  • המערך מלא בנתונים חוקיים (כלומר רק 0 ו-1) והוא אינו null.
  • המערך סימטרי סביב האלכסון הראשי, כלומר לכל i,j בגבולות המערך, מתקיים mat[i][j] == mat[j][i].
  • באלכסון הראשי של המערך יש 0, כלומר לכל i בגבולות המערך מתקיים mat[i][i] = 0.

אם אין מעגלי היכרות באורך 3 בכלל במערך, השיטה כמובן תחזיר 0 ולא תדפיס כלום.

יש להחזיר את מספר מעגלי ההיכרות וגם להדפיס את כל המעגלים.

דוגמה 1:
קלט: 
matrix =
[[0, 1, 0, 0, 0, 1, 1, 0, 0, 0],
 [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
 [0, 1, 0, 0, 0, 1, 1, 0, 0, 1],
 [0, 1, 0, 0, 0, 0, 1, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 1, 0, 0, 0, 0, 1, 1, 0],
 [1, 0, 1, 1, 0, 0, 0, 1, 1, 0],
 [0, 0, 0, 1, 0, 1, 1, 0, 0, 1],
 [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
 [0, 1, 1, 0, 1, 0, 0, 1, 0, 0]]
פלט: 
1 2 9
3 6 7
2

הסבר: יש בדיוק שני מעגלי היכרות באורך 3: הראשון בין האנשים שמספריהם 1, 2 ו-9 והשני בין האנשים שמספריהם 3, 6 ו-7.

דוגמה 2:
קלט: 
matrix =
[[0, 1, 1, 1],
 [1, 0, 1, 1],
 [1, 1, 0, 1],
 [1, 1, 1, 0]]
פלט: 
0 1 2
0 1 3
0 2 3
1 2 3
4

הסבר: יש ארבעה מעגלי היכרות באורך 3.

דוגמה 3:
קלט: 
matrix =
[[0, 1, 1, 0, 0],
 [1, 0, 0, 1, 0],
 [1, 0, 0, 1, 1],
 [0, 1, 1, 0, 1],
 [0, 0, 1, 1, 0]]
פלט: 
2 3 4
1

הסבר: יש מעגל היכרות אחד באורך 3 בין האנשים שמספריהם 2, 3 ו-4 בלבד.

דוגמה 4:
קלט: 
matrix =
[[0, 1, 0, 0, 0, 0],
 [1, 0, 1, 0, 0, 0],
 [0, 1, 0, 1, 0, 0],
 [0, 0, 1, 0, 1, 0],
 [0, 0, 0, 1, 0, 1],
 [0, 0, 0, 0, 1, 0]]
פלט: 
0

הסבר: במטריצה זו אין מעגלי היכרות באורך 3. המטריצה מייצגת גרף בצורת שרשרת שבו כל אדם מכיר רק את הסמוכים לו.

דוגמה 5:
קלט: 
matrix =
[[0, 1, 1, 1, 1],
 [1, 0, 1, 1, 1],
 [1, 1, 0, 1, 1],
 [1, 1, 1, 0, 1],
 [1, 1, 1, 1, 0]]
פלט: 
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
10

הסבר: במטריצה זו כל אדם מכיר את כל האחרים, ולכן יש בדיוק 10 מעגלי היכרות שונים באורך 3 (מספר הקומבינציות האפשריות מתוך 5 אנשים לבחור 3).

דוגמה 6:
קלט: 
matrix =
[[0, 1, 0, 1],
 [1, 0, 1, 0],
 [0, 1, 0, 1],
 [1, 0, 1, 0]]
פלט: 
0

הסבר: במטריצה זו אין מעגלי היכרות באורך 3. המטריצה מייצגת גרף דו-צדדי שבו אין מעגלי היכרות של מספר אי-זוגי של אנשים.

דוגמה 7:
קלט: 
matrix =
[[0, 1, 1, 0, 1],
 [1, 0, 1, 1, 0],
 [1, 1, 0, 1, 1],
 [0, 1, 1, 0, 1],
 [1, 0, 1, 1, 0]]
פלט: 
0 1 2
0 2 4
1 2 3
2 3 4
4

הסבר: יש ארבעה מעגלי היכרות באורך 3 במטריצה זו. האדם מספר 2 מופיע בכל המעגלים, כיוון שהוא מכיר את כל האחרים.

דוגמה 8:
קלט: 
matrix =
[[0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0]]
פלט: 
0

הסבר: במטריצה זו אין היכרויות כלל, ולכן אין מעגלי היכרות מכל אורך שהוא.

Loading...
נשמרLn 1, Col 1

קלט:

matrix =
[[0, 1, 0, 0, 0, 1, 1, 0, 0, 0],
 [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
 [0, 1, 0, 0, 0, 1, 1, 0, 0, 1],
 [0, 1, 0, 0, 0, 0, 1, 1, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
 [1, 0, 1, 0, 0, 0, 0, 1, 1, 0],
 [1, 0, 1, 1, 0, 0, 0, 1, 1, 0],
 [0, 0, 0, 1, 0, 1, 1, 0, 0, 1],
 [0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
 [0, 1, 1, 0, 1, 0, 0, 1, 0, 0]]

הפלט המבוקש:

1 2 9
3 6 7
2