Surface – solution CodinGame en Java
Pour résoudre Surface, on voit la carte comme un graphe en grille où chaque case d'eau 'O' est reliée à ses quatre voisines orthogonales, et on répond à chaque requête par la taille de la composante connexe contenant la case demandée (0 si c'est de la terre). On utilise un flood fill en BFS itératif plutôt que récursif, et on étiquette chaque lac une seule fois pour que les requêtes répétées sur le même lac ne coûtent rien. Avec l'étiquetage, le tout est en O(L·H + N).
L'énoncé
On reçoit une carte rectangulaire de largeur L et de hauteur H composée de '#' (terre) et de 'O' (eau), puis N coordonnées (X, Y). Pour chaque coordonnée, il faut afficher l'aire du lac qui la contient, un lac étant un groupe de cases d'eau reliées par leurs côtés, jamais en diagonale. Si la coordonnée tombe sur la terre, la réponse est 0.
Les cartes peuvent être grandes et les requêtes nombreuses, et plusieurs requêtes visent souvent le même lac : le coût du recalcul répété d'une même région compte autant que le flood fill lui-même.
La démarche, étape par étape
- Lire la grille ligne par ligneOn lit L et H, puis H lignes de exactement L caractères. On indexe les cases en grid[y][x] : l'entrée donne d'abord X (la colonne) puis Y (la ligne), inversion facile à commettre.
- Flood fill avec une file expliciteDepuis la case demandée, si c'est un 'O', on l'empile dans une file, on la marque visitée, puis on défile une case à la fois en examinant ses quatre voisines. Toute voisine dans la carte, en eau et non visitée est marquée et enfilée ; le compteur de cases marquées est l'aire du lac.
- Jamais de récursion sur les grands lacsUn DFS récursif descend aussi profond que le lac est grand : un lac de quelques centaines de milliers de cases fait déborder la pile d'appels en Java, C++ ou Python. Une ArrayDeque ou un simple tableau d'entiers utilisé comme file évite complètement le problème.
- Étiqueter les lacs une fois, répondre depuis un cachePlutôt que de copier la carte à chaque requête, on garde un tableau d'étiquettes initialisé à -1. Quand une requête tombe sur une case d'eau non étiquetée, on la remplit une fois, on écrit l'identifiant du lac dans chaque case et on stocke l'aire dans une liste. Une requête ultérieure sur le même lac devient une simple lecture de tableau.
- Afficher un nombre par requêteOn affiche l'aire de chaque requête sur sa propre ligne, dans l'ordre où les requêtes ont été données.
Complexité
O(L·H + N) with labellingO(L·H)Chaque case d'eau est visitée par au plus un flood fill et chaque requête est une lecture en temps constant. Le code Java publié refait le remplissage sur une copie fraîche à chaque requête, ce qui donne O(N·L·H) dans le pire cas.
Code de la solution
Surface – Java
La solution Java utilise une petite classe Coords et une LinkedList comme file de BFS, et copie toute la carte avant chaque requête pour que les cases remplies ('#') ne fuient pas d'une requête à l'autre. Correct et lisible, mais sur de grandes cartes avec beaucoup de requêtes, cette copie par requête est la première chose à remplacer par un tableau d'étiquettes.
import java.util.*;
import java.io.*;
import java.math.*;
class Solution {
/** width, height of the map and the map*/
static private int width;
static private int height;
static private char[][] map;
/** Class representing a couple of cartesian coordinates*/
static class Coords {
int X, Y;
public Coords(int X, int Y){
this.X = X;
this.Y = Y;
}
/** returns an array containing the 4 adjacent coordinates to this */
public Coords[] neighbours() {
Coords res[] = {new Coords(X, Y-1), new Coords(X+1, Y), new Coords(X, Y+1), new Coords(X-1, Y)};
return res;
}
/** returns true if and only if the coordinates are in the boundaries of the map*/
public boolean isInMap() {
return 0 <= X && X < width && 0 <= Y && Y < height;
}
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
// Reads the map
width = in.nextInt();
height = in.nextInt();
in.nextLine();
map = new char[height][width];
for (int y = 0; y < height; y++)
map[y] = in.nextLine().toCharArray();
int N = in.nextInt();
for (int i = 0; i < N; i++) {
int X = in.nextInt();
int Y = in.nextInt();
// copies the map
char[][] copy = new char[height][width];
for (int y = 0; y < height; y++)
for (int x = 0; x < width; x++)
copy[y][x] = map[y][x];
// floods the map starting from (X,Y),
// counting the number of cells flooded, which is the area of the lake
LinkedList<Coords> queue = new LinkedList<Coords>();
int count = 0;
if (copy[Y][X] == 'O') {
copy[Y][X] = '#';
count++;
queue.add(new Coords(X, Y));
}
while (queue.size() > 0) {
Coords c = queue.remove();
for (Coords neighbour : c.neighbours()) {
if (neighbour.isInMap() && copy[neighbour.Y][neighbour.X] == 'O') {
copy[neighbour.Y][neighbour.X] = '#';
count++;
queue.add(neighbour);
}
}
}
System.out.println(count);
}
}
}
Erreurs fréquentes
- Débordement de pile avec un DFS récursifL'échec le plus fréquent : la profondeur de récursion égale la taille du lac, et une carte presque entièrement en eau dépasse facilement la pile par défaut du thread. Passez à une file ou une pile explicite.
- Inverser X et YLes requêtes donnent la colonne d'abord, la ligne ensuite. Accéder à grid[X][Y] marche sur les cartes carrées des tests et casse silencieusement sur les rectangulaires, souvent avec un dépassement d'indice.
- Compter les voisines diagonalesSeuls le haut, le bas, la gauche et la droite relient l'eau. Avec 8 directions, on fusionne des lacs qui ne se touchent que par un coin et on renvoie des aires trop grandes.
- Modifier la carte partagée entre les requêtesSi vous écrasez 'O' par '#' pour marquer les visites sur la carte d'origine, la requête suivante sur le même lac renvoie 0. Utilisez une structure de visite séparée, réinitialisez-la, ou mettez le résultat en cache par lac.
- Dépassement de temps par remplissages répétésQuand des milliers de requêtes visent le même lac géant, le recalculer à chaque fois est du gaspillage. Mettez l'aire en cache par composante.
Pour aller plus loin
Comme la carte ne change jamais, Surface est en réalité un problème de composantes connexes déguisé en problème de requêtes. On pourrait même étiqueter tous les lacs d'avance en un seul passage sur la grille, mais l'étiquetage paresseux (seulement quand une requête touche une case non étiquetée) est aussi rapide dans le pire cas et plus rapide quand les requêtes ne touchent que peu de lacs. Une autre option qui marche très bien est l'union-find : on unit chaque case d'eau avec ses voisines d'eau de droite et du dessous en un seul balayage, puis l'aire du lac est la taille de la racine de la case. L'union-find n'a besoin d'aucune file, ce qui en fait une belle alternative dans les langages où les files sont pénibles, et il répond naturellement à n'importe quel nombre de requêtes en temps quasi constant.
Questions fréquentes
Faut-il un BFS ou un DFS pour Surface ?
Les deux visitent les mêmes cases, donc l'aire est identique. Ce qui compte, c'est d'éviter la récursion : un BFS itératif avec une file ou un DFS itératif avec une pile restent sûrs sur les très grands lacs.
Que faut-il afficher quand la case demandée est de la terre ?
Il faut afficher 0. Une case de terre n'appartient à aucun lac, donc son aire est nulle.
Pourquoi ma solution Surface passe les petits tests mais échoue sur les grands ?
Typiquement un débordement de pile dû à un flood fill récursif, ou un dépassement de temps parce que le même grand lac est rempli à chaque requête. Utilisez une file explicite et mettez l'aire de chaque lac en cache.