Surface – CodinGame solution in Java
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
- 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.
- 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.
- 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.
- 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.
- Print one number per queryOutput the area for each query on its own line, in the order the queries were given.
Complexity
O(L·H + N) with labellingO(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
- Stack overflow from recursive DFSThe most common failure: recursion depth equals lake size, and a map that is almost all water easily exceeds the default thread stack. Switch to an explicit queue or stack.
- Swapping X and YQueries give the column first and the row second. Accessing grid[X][Y] works on square test maps and silently breaks on rectangular ones, often with an index out of bounds.
- Counting diagonal neighboursOnly up, down, left and right connect water. Using 8 directions merges lakes that touch only at corners and returns areas that are too large.
- Mutating the shared map between queriesIf you overwrite 'O' with '#' to mark visits on the original map, the next query on the same lake returns 0. Either use a separate visited structure, reset it, or cache the result per lake.
- Timeout from repeated full floodsWhen thousands of queries hit the same giant lake, recomputing it each time is wasteful. Cache the area per component.
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.