Coding Solution

Surface – solution CodinGame en Java

Difficileflood fillBFSconnected componentsgridMis à jour le
Réponse courte

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

  1. 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.
  2. 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.
  3. 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.
  4. É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.
  5. 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é

TempsO(L·H + N) with labelling
MémoireO(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

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.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome