22ος ΠΔΠ B' Φάση: Οι φωτιές στην Ελλάδα (fire) - Λύση

Επεξήγηση εκφώνησης

Μας δίνεται ένα πλέγμα (grid) με δύο τύπους κόμβων (“.” και “@”) και ένα σημείο \(c\) τύπου “.” πάνω στο πλέγμα. Πρέπει να μετρήσουμε το πλήθος των “.” που μπορουμε να φτάσουμε από το \(c\) ακολουθώντας μόνο “.”.

Η ιδέα είναι να μοντελοποίησουμε το πρόβλημα ως γράφο όπου υπάρχουν συνδέσεις μόνο μεταξύ γειτονικών σημείων τύπου “.”. Επομένως, ψάχνουμε για το μέγεθος του component στο οποίο ανήκει το \(c\). Για το παράδειγμα, αυτό φαίνεται στο παρακάτω σχήμα με πράσινο χρώμα (περιλαμβάνει 12 κόμβους):

Αναζήτηση κατά βάθος με αναδρομή

Ο κλασσικός αλγόριθμος για την μέτρηση των κόμβων που μπορούμε να φτάσουμε από κάποιον άλλο κόμβο είναι η αναζήτηση κατά βάθος (DFS). Για αυτόν τον αλγόριθμο, υπάρχει η αναδρομική και η iterative υλοποίηση. Και οι δύο υλοποίησεις χρειάζονται χρόνο και μνήμη \(\mathcal{O}(NM)\). Η αναδρομική είναι λίγο πιο απλή στην υλοποίηση, αλλά μπορεί να οδηγήσει τη στοίβα των κλήσεων (call stack) να κάνει stack overflow (δηλαδή να ξεπεράσει το μέγεθος της call stack που διατεθεί στο πρόγραμμα). Η iterative λύση το αποφεύγει αυτό χρησιμοποιώντας μία στοίβα (stack) ως δομή δεδομένων. Στα δοσμένα testcases και σε κάποια συστήματα, η recursive DFS δεν περνάει το 3ο testcase, που είναι ειδικά σχεδιασμένο για αυτόν τον σκοπό.

Στην παρακάτω υλοποίηση, για να αποφύγουμε τους ελέγχους αν είμαστε στα όρια του πίνακα, βάζουμε @ γύρω γύρω από τον πίνακα, τα οποία μας απαγορεύουν να τα προσπεράσουμε.

#include <algorithm>
#include <cstdio>
#include <vector>

const int MAXN = 1'000;

// +2 γιατί βάζουμε το ψεύτικο περίγραμμα από @.
char grid[MAXN+2][MAXN+2];
bool visited[MAXN+2][MAXN+2]; 

// Πίνακας για να βρίσκουμε πιο εύκολα τους γειτονικούς κόμβους.
// Οι γειτονικοί κομβοι του (x, y), είναι (x,y+1), (x+1,y), (x-1,y), (x,y-1).
std::vector<std::pair<int, int>> ds({ {0, 1}, {1, 0}, {-1, 0}, {0, -1} });

int dfs(int x, int y) {
   if (visited[x][y]) return 0;
   visited[x][y] = true;
   int total = 1;
   for (auto [dx, dy] : ds) {
      if (!visited[x+dx][y+dy] && grid[x+dx][y+dy] != '@')
         total += dfs(x+dx,y+dy);
   }
   return total;
}

int main() {
   FILE *fi = fopen("fire.in", "r");
   int N, M, Nf, Mf;
   fscanf(fi, "%d %d\n", &N, &M);
   fscanf(fi, "%d %d\n", &Nf, &Mf);
   for (int i = 1; i <= M; ++i) {
      for (int j = 1; j <= N; ++j) {
         fscanf(fi, "%c", &grid[i][j]);
      }
      fscanf(fi, "\n");
   }
   fclose(fi);
   
   // Δημιουργούμε το ψεύτικο περίγραμμα.
   for (int i = 0; i <= M + 1; ++i) grid[i][0] = grid[i][N+1] = '@';
   for (int i = 0; i <= N + 1; ++i) grid[0][i] = grid[M+1][i] = '@';
   
   FILE *fo = fopen("fire.out", "w");
   fprintf(fo, "%ld\n", dfs(Mf, Nf));
   fclose(fo);
   
   return 0;
}

Iterative αναζήτηση κατά βάθος

#include <algorithm>
#include <cstdio>
#include <stack>
#include <vector>

const int MAXN = 1'000;

// +2 γιατί βάζουμε το ψεύτικο περίγραμμα από @.
char grid[MAXN+2][MAXN+2];
bool visited[MAXN+2][MAXN+2]; 

std::vector<std::pair<int, int>> ds({ {0, 1}, {1, 0}, {-1, 0}, {0, -1} });

int dfs(int x0, int y0) {
   std::stack<std::pair<int, int>> st;
   st.push({ x0, y0 });
   visited[x0][y0] = true;
   int total = 0;
   while(!st.empty()) {
      auto [x,y] = st.top();
      st.pop();
      ++total;
      for (auto [dx, dy] : ds) {
         if (!visited[x+dx][y+dy] && grid[x+dx][y+dy] != '@') {
            visited[x+dx][y+dy] = true;
            st.push({ x+dx, y+dy });
         }
      }
   }
   return total;
}

int main() {
   FILE *fi = fopen("fire.in", "r");
   int N, M, Nf, Mf;
   fscanf(fi, "%d %d\n", &N, &M);
   fscanf(fi, "%d %d\n", &Nf, &Mf);
   for (int i = 1; i <= M; ++i) {
      for (int j = 1; j <= N; ++j) {
         fscanf(fi, "%c", &grid[i][j]);
      }
      fscanf(fi, "\n");
   }
   fclose(fi);
   
   // Δημιουργούμε το ψεύτικο περίγραμμα.
   for (int i = 0; i <= M + 1; ++i) grid[i][0] = grid[i][N+1] = '@';
   for (int i = 0; i <= N + 1; ++i) grid[0][i] = grid[M+1][i] = '@';
   
   FILE *fo = fopen("fire.out", "w");
   fprintf(fo, "%ld\n", dfs(Mf, Nf));
   fclose(fo);
   
   return 0;
}