Menu
Coddy logo textTech

פסגות

חלק מהיחידה יסודות במסלול ה-C של Coddy. שיעור 62 מתוך 63.

challenge icon

אתגר

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

כללים

  • 8 שכנים: יש לבדוק את הצפון, הדרום, המזרח, המערב ואת כל ארבעת האלכסונים.
  • תאי גבול: לתא שנמצא בקצה או בפינה יש פחות מ־8 שכנים. הוא עדיין פסגה אם הוא גדול ממש מכל שכניו הקיימים.
  • גדול ממש: אם לשכן יש אותו גובה כמו לתא הנוכחי, התא הנוכחי אינו פסגה.

קלט

  • שני מספרים שלמים N ו־M המייצגים את מספר השורות והעמודות.
  • רשת בגודל N*M של מספרים שלמים

פלט

  1. מספר שלם המייצג את המספר הכולל של הפסגות.
  2. הקואורדינטות (שורה ועמודה, באינדוקס מ־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 אונליין