二次元配列を特定条件で全捜査する（BFS）

コード（JavaScript）
1. ロジックの説明
BFSコードの解説

コード（JavaScript）

const COLS = 10, ROWS = 20, SZ = 20;
function newBoard() { return Array.from({ length: ROWS }, () => Array(COLS).fill(0)); }
board = newBoard();

    function checkElLevelUp() {
      // 重複対策
      const visited = Array.from({ length: ROWS }, () => Array(COLS).fill(false));

      for (let r = 0; r < ROWS; r++) {
        for (let c = 0; c < COLS; c++) {          
          if (!board[r][c] || visited[r][c]) continue;

          const el = board[r][c].magicEl;
          const group = [];
          const queue = [[r, c]];
          visited[r][c] = true;

          // BFSで隣接する同じmagicElのセルをグループ化
          while (queue.length) {
            const [cr, cc] = queue.shift();
            group.push([cr, cc]);

            // 上下左右を調べてボード内かつ調べてなければ捜査続行
            for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
              const nr = cr + dr, nc = cc + dc;
              if (
                nr >= 0 && nr < ROWS &&
                nc >= 0 && nc < COLS &&
                !visited[nr][nc] &&
                board[nr][nc] &&
                board[nr][nc].magicEl === el
              ) {
                visited[nr][nc] = true;
                queue.push([nr, nc]);
              }
            }
          }

          // 10個以上で elLevel を +1（上限2）
          if (group.length >= 10) {
            group.forEach(([gr, gc]) => {
              board[gr][gc].elLevel = Math.min(board[gr][gc].elLevel + 1, 2);
            });
          }
        }
      }
    }

const COLS = 10, ROWS = 20, SZ = 20;

function newBoard() { return Array.from({ length: ROWS }, () => Array(COLS).fill(0)); }

board = newBoard();

function checkElLevelUp() {

// 重複対策

const visited = Array.from({ length: ROWS }, () => Array(COLS).fill(false));

for (let r = 0; r < ROWS; r++) {

for (let c = 0; c < COLS; c++) {

if (!board[r][c] || visited[r][c]) continue;

const el = board[r][c].magicEl;

const group = [];

const queue = [[r, c]];

visited[r][c] = true;

// BFSで隣接する同じmagicElのセルをグループ化

while (queue.length) {

const [cr, cc] = queue.shift();

group.push([cr, cc]);

// 上下左右を調べてボード内かつ調べてなければ捜査続行

for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {

const nr = cr + dr, nc = cc + dc;

if (

nr >= 0 && nr < ROWS &&

nc >= 0 && nc < COLS &&

!visited[nr][nc] &&

board[nr][nc] &&

board[nr][nc].magicEl === el

) {

visited[nr][nc] = true;

queue.push([nr, nc]);

}

// 10個以上で elLevel を +1（上限2）

if (group.length >= 10) {

group.forEach(([gr, gc]) => {

board[gr][gc].elLevel = Math.min(board[gr][gc].elLevel + 1, 2);

});

}

ロジックの説明

ステップ	内容
① visited配列	同じセルを二重チェックしないよう管理
② BFS	上下左右に隣接し、かつ同じ`magicEl`のセルを再帰的に収集
③ グループ判定	収集したセル数が10以上なら対象グループ全体に処理
④ elLevelアップ	`Math.min(...+ 1, 2)` でキャップ制限

BFSコードの解説

まず全体の「考え方」

BFS（幅優先探索）は 「近い場所から順番に探索する」 アルゴリズムです。池に石を投げたときの波紋のように、起点から隣へ隣へと広がっていくイメージです。

queue（待ち行列）とは

const queue = [[r, c]];

1	const queue = [[r, c]];

queue は「次に調べるべき座標を並べた列」です。最初は起点のセル [r, c] だけが入っています。

queue = [ [2, 3] ]   // まず (行2, 列3) を調べる予定

1	queue = [ [2, 3] ] // まず (行2, 列3) を調べる予定

queue.shift() とは

const [cr, cc] = queue.shift();

1	const [cr, cc] = queue.shift();

shift() は配列の先頭を1つ取り出すメソッドです。

queue.shift() の動作イメージ：

実行前： queue = [ [2,3], [2,4], [3,3] ]
                    ↑ここを取り出す

実行後： queue = [ [2,4], [3,3] ]
戻り値：  [2, 3]

queue.shift() の動作イメージ：

実行前： queue = [ [2,3], [2,4], [3,3] ]

↑ここを取り出す

実行後： queue = [ [2,4], [3,3] ]

戻り値： [2, 3]

const [cr, cc] = とは（分割代入）

これが「難しい」と感じた部分ですね。分割代入（Destructuring） という構文です。

// 普通の書き方
const pair = queue.shift();  // pair = [2, 3]
const cr = pair[0];          // cr = 2
const cc = pair[1];          // cc = 3

// ↓ これを1行で書けるのが分割代入
const [cr, cc] = queue.shift();
//     ↑  ↑
//     cr=2, cc=3  （配列の順番通りに変数に入る）

// 普通の書き方

const pair = queue.shift(); // pair = [2, 3]

const cr = pair[0]; // cr = 2

const cc = pair[1]; // cc = 3

// ↓ これを1行で書けるのが分割代入

const [cr, cc] = queue.shift();

// ↑ ↑

// cr=2, cc=3 （配列の順番通りに変数に入る）

cr は current row（現在の行）、cc は current col（現在の列）です。

ループ全体の流れ

while (queue.length) {          // queueが空になるまで繰り返す
  const [cr, cc] = queue.shift(); // 先頭の座標を取り出す
  group.push([cr, cc]);           // グループに追加（確定）

  // 上下左右の4方向を調べる
  for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
    const nr = cr + dr;  // 隣のセルの行
    const nc = cc + dc;  // 隣のセルの列

    if ( /* 範囲内 && 未訪問 && 同じmagicEl */ ) {
      visited[nr][nc] = true;  // 訪問済みにマーク
      queue.push([nr, nc]);    // queueに追加（後で調べる）
    }
  }
}

while (queue.length) { // queueが空になるまで繰り返す

const [cr, cc] = queue.shift(); // 先頭の座標を取り出す

group.push([cr, cc]); // グループに追加（確定）

// 上下左右の4方向を調べる

for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {

const nr = cr + dr; // 隣のセルの行

const nc = cc + dc; // 隣のセルの列

if ( /* 範囲内 && 未訪問 && 同じmagicEl */ ) {

visited[nr][nc] = true; // 訪問済みにマーク

queue.push([nr, nc]); // queueに追加（後で調べる）

}

具体的な動きはこうなります：

起点 (2,3) が 🔥 だとして…

Step1: queue=[[2,3]]
       → (2,3)を取り出してgroupに追加
       → 隣の(1,3)(3,3)(2,2)(2,4)を調べて🔥ならqueueに追加
       → queue=[[1,3],[2,4]]  ※(3,3)(2,2)は別の属性だったとする

Step2: queue=[[1,3],[2,4]]
       → (1,3)を取り出してgroupに追加
       → (1,3)の隣を調べて…
       → queue=[[2,4],[1,4]]

Step3: ...queueが空になるまで繰り返す

起点 (2,3) が 🔥 だとして…

Step1: queue=[[2,3]]

→ (2,3)を取り出してgroupに追加

→ 隣の(1,3)(3,3)(2,2)(2,4)を調べて🔥ならqueueに追加

→ queue=[[1,3],[2,4]] ※(3,3)(2,2)は別の属性だったとする

Step2: queue=[[1,3],[2,4]]

→ (1,3)を取り出してgroupに追加

→ (1,3)の隣を調べて…

→ queue=[[2,4],[1,4]]

Step3: ...queueが空になるまで繰り返す

visited に「調べた印」をつけておくことで、同じセルを二度調べないのがポイントです。