Codingame Solution: Surface

Solution

This problem is pretty nice. It's really easy to implement but due to the size of the grid and the maximum number of test cases, this one becomes quite interesting. My first idea was generating a map, where each cell contains the size of the adjacent water area. This would be the fastest when it comes to execution time, but uses tremendous amounts of memory (1000x1000 grid with 4 byte per cell). Also creating a map like this would be really slow.

The next idea was using a flood fill algorithm. The recursive implementation could have the problem of stack overflows on large water areas, so I decided to go with a stack based version. When we get a cell-coordinate, we push it on a stack and check if that coordinate was water. If it was, we can increment the area counter and push all adjacent cells on the stack. We also mark the already visited spot with an X to not come into an endless loop:

function getWaterArea(map, x, y) {

  var stack = [[x, y]];
  var cnt = 0;

  while (stack.length > 0) {
    [x, y] = stack.pop();

    if (map[y] && map[y][x] === 'O') {
      map[y][x] = 'X';
      cnt++;
      stack.push([x, y + 1]);
      stack.push([x, y - 1]);
      stack.push([x + 1, y]);
      stack.push([x - 1, y]);
    }
  }
  return cnt;
}

When executing this algorithm, we need to make sure that the two dimensional array is copied for every iteration, so that we have a clean map all the time. I now made several optimizations. 1. I stored the map in a one-dimensional typed array with the small additional cost of coordinate calculation, but loss of loads of array creations. 2. I removed the array creation and added another loop which was resetting every marked cell. I also added checks before adding new coordinates to the stack, if they are valid. The final clou was removing the cleaning loop by passing the index of the current test case (offsetted by two). This allows the identification of a marked cell of the current test case. All in all, this is what I came up with, after all the optimizations:

function _(x, y) {
  return y * L + x;
}

function getWaterArea(map, x, y, ndx) {

  var stack = [_(x, y)];
  var cnt = 0;

  while (stack.length > 0) {
    var c = stack.pop();

    if (map[c] !== 0 && map[c] !== ndx) {
      map[c] = ndx;

      x = c % L;
      y = c / L | 0;

      if (y + 1 < H) stack.push(_(x, y + 1));
      if (y > 0)     stack.push(_(x, y - 1));
      if (x + 1 < L) stack.push(_(x + 1, y));
      if (x > 0)     stack.push(_(x - 1, y));
      cnt++;
    }
  }
  return cnt;
}

var L = +readline();
var H = +readline();

var M = new Uint16Array(L * H);

for (var y = 0; y < H; y++) {
  var line = readline();
  for (var x = 0; x < L; x++) {
    M[_(x, y)] = line[x] === 'O';
  }
}

var N = +readline();
for (var y = 0; y < N; y++) {
  var inputs = readline().split(' ');
  print(getWaterArea(M, +inputs[0], +inputs[1], y + 2));
}