פסגות
חלק מהיחידה יסודות במסלול ה-C של Coddy. שיעור 62 מתוך 63.
אתגר
נתונה לך רשת דו־ממדית של גבהים שלמים המייצגת מפה של שטח. תא נקרא פסגה אם הערך שלו גדול ממש מכל השכנים הסמוכים שלו (עד 8: צפון, דרום, מזרח, מערב וארבעת האלכסונים).
כללים
- 8 שכנים: יש לבדוק את הצפון, הדרום, המזרח, המערב ואת כל ארבעת האלכסונים.
- תאי גבול: לתא שנמצא בקצה או בפינה יש פחות מ־8 שכנים. הוא עדיין פסגה אם הוא גדול ממש מכל שכניו הקיימים.
- גדול ממש: אם לשכן יש אותו גובה כמו לתא הנוכחי, התא הנוכחי אינו פסגה.
קלט
- שני מספרים שלמים
Nו־Mהמייצגים את מספר השורות והעמודות. - רשת בגודל
N*Mשל מספרים שלמים
פלט
- מספר שלם המייצג את המספר הכולל של הפסגות.
- הקואורדינטות (שורה ועמודה, באינדוקס מ־0) של כל פסגה, ממוינות קודם לפי שורה ואז לפי עמודה.
לדוגמה, עבור הקלט הזה:
5 5
1 2 1 3 4
5 1 1 1 1
1 1 9 1 1
2 1 1 1 2
1 3 1 4 1זה הפלט:
5
0 4
1 0
2 2
4 1
4 3הסבר הפסגות נמצאות במיקומים הבאים:
- (0,4) בגובה 4: גבוה מהשכנים (3, 1, 1).
- (1,0) בגובה 5: גבוה מהשכנים (1, 2, 1, 1, 1).
- (2,2) בגובה 9: גבוה מכל שמונת ה־1 שמסביבו.
- (4,1) בגובה 3: גבוה מהשכנים (2, 1, 1, 1, 1).
- (4,3) בגובה 4: גבוה מהשכנים (1, 1, 1, 2, 1).
נסו בעצמכם
#include <stdio.h>
#define MAXN 100
#define MAXM 100
int N, M;
int grid[MAXN][MAXM];
/**
* מחזירה 1 אם התא ב-(r, c) הוא שיא, ו-0 אחרת.
* שיא חייב להיות גדול ממש מכל שכניו הקיימים.
*/
int is_peak(int r, int c) {
// TODO: הגדירו את המיקומים היחסיים של 8 השכנים
// (צפון, דרום, מזרח, מערב ו-4 הכיוונים האלכסוניים).
// TODO: עברו על כל שכן.
// רמז חשוב: לפני שבודקים את grid[nr][nc], חובה לוודא
// ש-nr ו-nc נמצאים בגבולות (0 עד N-1 ו-0 עד M-1).
return 1; // ממלא מקום
}
int main() {
// קראו את הממדים
if (scanf("%d %d", &N, &M) != 2) {
return 1;
}
// TODO: קראו את ערכי הרשת מ-stdin באמצעות לולאות מקוננות.
// TODO: עברו על כל תא (i, j) ברשת.
// אם is_peak(i, j) מחזירה true, שמרו את הקואורדינטות.
// אפשר להשתמש בשני מערכים כמו peak_r[MAXN*MAXM] ו-peak_c[MAXN*MAXM]
// כדי לשמור את התוצאות לפני ההדפסה.
// TODO: הדפיסו את המספר הכולל של הפסגות.
// TODO: הדפיסו כל זוג (row, col) שנשמר.
// מכיוון שעוברים תחילה על השורות ואחר כך על העמודות, הזוגות כבר יהיו ממוינים!
return 0;
}כל השיעורים ביחידה יסודות
תרגלו בעצמכם: קומפיילר C אונליין