課題 · アルゴリズム中級 JavaScript ·

Count islands

The map is a list of equal-length strings; "#" is land and "." is water. Land cells connected horizontally or vertically (not diagonally) form one island. Return the number of islands. Maps can be up to 700×700, and a single island can cover the whole map.

シグネチャ

/**
 * @param {string[]} grid
 * @returns {number}
 */
function count_islands(grid)

入力例

count_islands(["##...", "##...", "..#..", "...##"])  // -> 3
count_islands([".#.", "###", ".#."])  // -> 1

その他、入力値が非公開の7個の非公開テストおよび制限時間付きの2個の大規模入力テストがあります。モデルへの課題は英語で出題されます。

#1Anthropic Claude Sonnet 5.5正解 · 11 / 11 件のテストにパス回答時間 5.4 秒 · 実行時間 140 ms · $0.0093

✓	count_islands(["##...", "##...", "..#..", "...##"])期待値 3	2 ms
✓	count_islands([".#.", "###", ".#."])期待値 1	<1 ms

✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms✓ <1 ms⏱ 101 ms⏱ 28 ms

コード

function count_islands(grid) {
  const h = grid.length;
  if (h === 0) return 0;
  const w = grid[0].length;
  if (w === 0) return 0;
  const n = h * w;
  const a = new Uint8Array(n);
  for (let i = 0; i < h; i++) {
    const s = grid[i];
    const base = i * w;
    const l = Math.min(w, s.length);
    for (let j = 0; j < l; j++) {
      if (s.charCodeAt(j) === 35) a[base + j] = 1;
    }
  }
  const stack = new Int32Array(n);
  let count = 0;
  for (let start = 0; start < n; start++) {
    if (a[start] === 0) continue;
    count++;
    a[start] = 0;
    let sp = 0;
    stack[sp++] = start;
    while (sp > 0) {
      const c = stack[--sp];
      const col = c % w;
      if (c >= w && a[c - w]) { a[c - w] = 0; stack[sp++] = c - w; }
      if (c + w < n && a[c + w]) { a[c + w] = 0; stack[sp++] = c + w; }
      if (col > 0 && a[c - 1]) { a[c - 1] = 0; stack[sp++] = c - 1; }
      if (col < w - 1 && a[c + 1]) { a[c + 1] = 0; stack[sp++] = c + 1; }
    }
  }
  return count;
}

#2SpaceXAI Grok 4.7正解 · 11 / 11 件のテストにパス回答時間 35 秒 · 実行時間 217 ms · $0.02

✓	count_islands(["##...", "##...", "..#..", "...##"])期待値 3	3 ms
✓	count_islands([".#.", "###", ".#."])期待値 1	2 ms

✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms⏱ 171 ms⏱ 35 ms

コード

function count_islands(grid) {
    const rows = grid.length;
    if (rows === 0) return 0;
    const cols = grid[0].length;
    if (cols === 0) return 0;
    const n = rows * cols;
    const visited = new Uint8Array(n);
    const queue = new Int32Array(n);
    let count = 0;
    for (let i = 0; i < rows; i++) {
        const rowStr = grid[i];
        const base = i * cols;
        for (let j = 0; j < cols; j++) {
            if (rowStr[j] === '#' && visited[base + j] === 0) {
                count++;
                let head = 0;
                let tail = 0;
                queue[tail++] = base + j;
                visited[base + j] = 1;
                while (head < tail) {
                    const pos = queue[head++];
                    const r = (pos / cols) | 0;
                    const c = pos - r * cols;
                    if (r > 0) {
                        const up = pos - cols;
                        if (visited[up] === 0 && grid[r - 1][c] === '#') {
                            visited[up] = 1;
                            queue[tail++] = up;
                        }
                    }
                    if (r + 1 < rows) {
                        const down = pos + cols;
                        if (visited[down] === 0 && grid[r + 1][c] === '#') {
                            visited[down] = 1;
                            queue[tail++] = down;
                        }
                    }
                    if (c > 0 && visited[pos - 1] === 0 && grid[r][c - 1] === '#') {
                        visited[pos - 1] = 1;
                        queue[tail++] = pos - 1;
                    }
                    if (c + 1 < cols && visited[pos + 1] === 0 && grid[r][c + 1] === '#') {
                        visited[pos + 1] = 1;
                        queue[tail++] = pos + 1;
                    }
                }
            }
        }
    }
    return count;
}

#2OpenAI GPT-6 Luna正解 · 11 / 11 件のテストにパス回答時間 3.7 秒 · 実行時間 220 ms · $0.0003

✓	count_islands(["##...", "##...", "..#..", "...##"])期待値 3	2 ms
✓	count_islands([".#.", "###", ".#."])期待値 1	<1 ms

✓ <1 ms✓ 1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ 3 ms✓ <1 ms⏱ 131 ms⏱ 79 ms

コード

function count_islands(grid) {
  const rows = grid.length;
  if (rows === 0) return 0;

  const cols = grid[0].length;
  const size = rows * cols;
  const visited = new Uint8Array(size);
  const stack = new Int32Array(size);
  let islands = 0;

  for (let r = 0; r < rows; r++) {
    const row = grid[r];
    for (let c = 0; c < cols; c++) {
      const start = r * cols + c;
      if (row[c] !== '#' || visited[start]) continue;

      islands++;
      let top = 0;
      stack[top++] = start;
      visited[start] = 1;

      while (top > 0) {
        const cell = stack[--top];
        const x = cell % cols;

        if (x > 0) {
          const next = cell - 1;
          if (!visited[next] && grid[Math.floor(next / cols)][x - 1] === '#') {
            visited[next] = 1;
            stack[top++] = next;
          }
        }
        if (x + 1 < cols) {
          const next = cell + 1;
          if (!visited[next] && grid[Math.floor(next / cols)][x + 1] === '#') {
            visited[next] = 1;
            stack[top++] = next;
          }
        }
        if (cell >= cols) {
          const next = cell - cols;
          if (!visited[next] && grid[Math.floor(next / cols)][x] === '#') {
            visited[next] = 1;
            stack[top++] = next;
          }
        }
        if (cell + cols < size) {
          const next = cell + cols;
          if (!visited[next] && grid[Math.floor(next / cols)][x] === '#') {
            visited[next] = 1;
            stack[top++] = next;
          }
        }
      }
    }
  }

  return islands;
}

#2Qwen3.8 Max (0902)正解 · 11 / 11 件のテストにパス回答時間 26 秒 · 実行時間 234 ms · $0.0085

✓	count_islands(["##...", "##...", "..#..", "...##"])期待値 3	3 ms
✓	count_islands([".#.", "###", ".#."])期待値 1	1 ms

✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ 2 ms✓ 2 ms⏱ 134 ms⏱ 87 ms

コード

function count_islands(grid) {
    if (grid.length === 0) return 0;
    const rows = grid.length;
    const cols = grid[0].length;
    const visited = new Uint8Array(rows * cols);
    let count = 0;
    
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '#' && !visited[r * cols + c]) {
                count++;
                const queue = [r * cols + c];
                visited[r * cols + c] = 1;
                let head = 0;
                while (head < queue.length) {
                    const idx = queue[head++];
                    const cr = (idx / cols) | 0;
                    const cc = idx % cols;
                    if (cr > 0 && !visited[idx - cols] && grid[cr - 1][cc] === '#') {
                        visited[idx - cols] = 1;
                        queue.push(idx - cols);
                    }
                    if (cr < rows - 1 && !visited[idx + cols] && grid[cr + 1][cc] === '#') {
                        visited[idx + cols] = 1;
                        queue.push(idx + cols);
                    }
                    if (cc > 0 && !visited[idx - 1] && grid[cr][cc - 1] === '#') {
                        visited[idx - 1] = 1;
                        queue.push(idx - 1);
                    }
                    if (cc < cols - 1 && !visited[idx + 1] && grid[cr][cc + 1] === '#') {
                        visited[idx + 1] = 1;
                        queue.push(idx + 1);
                    }
                }
            }
        }
    }
    return count;
}

トークンコスト: $0.04 · 対戦の進行と評価方法について →