Coding Solution

Surface – CodinGame solution in Java

Hardflood fillBFSconnected componentsgridUpdated
Short answer

To solve Surface, treat the map as a grid graph where water cells 'O' are connected to their four orthogonal neighbours, and answer each query with the size of the connected component containing the queried cell (0 if it is land). Use an iterative BFS flood fill rather than recursion, and label each lake once so repeated queries on the same lake cost nothing.

The problem

You receive a rectangular map of width L and height H made of '#' (land) and 'O' (water). Then come N coordinates (X, Y). For each coordinate, print the area of the lake that contains it, where a lake is a group of water cells joined edge to edge, never diagonally. If the coordinate is on land, the answer is 0.

Maps can be large and queries numerous, and several queries often point into the same lake, so the cost of recomputing the same region again and again matters as much as the flood fill itself.

Approach, step by step

  1. Read the grid as character rowsRead L and H, then H lines of exactly L characters. Index cells as grid[y][x]: the input gives X first (column) and Y second (row), which is easy to swap by mistake.
  2. Flood fill with an explicit queueFrom the queried cell, if it is 'O', push it into a queue, mark it visited and repeatedly pop a cell, checking its four neighbours. Every neighbour inside the map that is water and not yet visited is marked and pushed; the counter of marked cells is the lake area.
  3. Never recurse on big lakesA recursive DFS goes as deep as the lake is large, so a lake of a few hundred thousand cells overflows the call stack in Java, C++ or Python. An ArrayDeque or a plain int array used as a queue avoids that entirely.
  4. Label lakes once, answer queries from a cacheInstead of copying the map for every query, keep an int label array initialised to -1. When a query lands on an unlabelled water cell, flood it once, write the lake id into every cell and store the area in a list. A later query on the same lake is then a single array lookup.
  5. Print one number per queryOutput the area for each query on its own line, in the order the queries were given.

Complexity

TimeO(L·H + N) with labelling
SpaceO(L·H)

Each water cell is visited by at most one flood fill and each query is a constant-time lookup. The posted Java code re-floods on a fresh copy for every query, which is O(N·L·H) in the worst case.

Solution code

Surface – Java

The Java solution uses a small Coords class and a LinkedList as BFS queue, and copies the whole map before each query so that flooded cells ('#') do not leak between queries. Correct and readable, but on huge maps with many queries the per-query copy is the first thing to replace with a label array.

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);
        }
    }
}
            

Common mistakes

Going further

Because the map never changes, Surface is really a connected-components problem disguised as a query problem. You could even label every lake up front in one pass over the grid, but labelling lazily (only when a query hits an unlabelled cell) is just as fast in the worst case and faster when queries touch few lakes. Another option that works well is union-find: union every water cell with its right and bottom water neighbours in a single scan, then the lake area is the size of the cell's root. Union-find needs no queue at all, which makes it a nice alternative in languages where queues are awkward, and it naturally answers any number of queries in near constant time.

FAQ

Should I use BFS or DFS for Surface?

Either visits the same cells, so the area is identical. What matters is avoiding recursion: an iterative BFS with a queue or an iterative DFS with a stack both stay safe on very large lakes.

What do I print when the queried cell is land?

Print 0. A land cell is not part of any lake, so its area is zero.

Why does my Surface solution pass small tests but fail the large ones?

Typically a stack overflow from recursive flood fill, or a timeout from re-flooding the same big lake for every query. Use an explicit queue and cache each lake's area.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome