【JavaScript】行列の中で最も長い連続する1のラインを見つける方法

問題の概要

本記事では、0と1のみで構成された2次元配列（バイナリ行列）の中から、最も長く連続する「1」のラインを見つけるJavaScript関数の実装方法を解説します。まず、次のようなバイナリ行列を例に考えてみましょう。

const arr = [
   [0,1,1,0],
   [0,1,1,0],
   [0,0,0,1]
];

作成する関数は、このような行列を第一引数（唯一の引数）として受け取ります。そして、水平・垂直・斜め・逆斜めのいずれかの方向に並んだ連続する「1」の最長ラインを検索し、そのラインに含まれる1の個数を返します。

上記の行列の場合、期待される出力は次の通りです。

const output = 3

これは、arr[0][1] の位置から始まる斜め方向のラインが、arr[2][3] まで3つ連続しており、これが最長となるためです。

アルゴリズムの考え方：動的計画法（DP）

この問題は、動的計画法（Dynamic Programming）を用いることで効率的に解くことができます。基本的なアプローチは以下の通りです。

• 各セルに対して、4つの方向（水平・垂直・斜め・逆斜め）それぞれについて「そのセルまでの連続する1の長さ」を記録するDPテーブルを作成します。
• セルの値が1である場合、進行方向にある直前のセルのDP値を参照し、長さを更新します。
• 処理の過程で全体の最大値を追跡し、最終的にその値を返します。

実装コード

実際のコードは以下のようになります。

const arr = [
   [0,1,1,0],
   [0,1,1,0],
   [0,0,0,1]
];
const longestLine = (arr = []) => {
   if(!arr.length){
      return 0;
   }
   let rows = arr.length, cols = arr[0].length;
   let res = 0;
   const dp = Array(rows).fill([]);
   dp.forEach((el, ind) => {
      dp[ind] = Array(cols).fill([]);
      dp[ind].forEach((undefined, subInd) => {
         dp[ind][subInd] = Array(4).fill(null);
      });
   });
   for (let i = 0; i < rows; i++) {
      for (let j = 0; j < cols; j++) {
         if (arr[i][j] == 1) {
            dp[i][j][0] = j > 0 ? dp[i][j - 1][0] + 1 : 1;
            dp[i][j][1] = i > 0 ? dp[i - 1][j][1] + 1 : 1;
            dp[i][j][2] = (i > 0 && j > 0) ? dp[i - 1][j - 1][2] + 1 : 1;
            dp[i][j][3] = (i > 0 && j < cols - 1) ? dp[i - 1][j + 1][3] + 1 : 1;
            res = Math.max(res, Math.max(dp[i][j][0], dp[i][j][1]));
            res = Math.max(res, Math.max(dp[i][j][2], dp[i][j][3]));
         };
      };
   };
   return res;
};
console.log(longestLine(arr));

コードのポイント

• DPテーブルの構造： dp[i][j] は4つの要素を持つ配列で、それぞれ「水平」「垂直」「斜め」「逆斜め」方向における連続する1の長さを格納します。
• 境界チェック： 各方向について行・列の端に達していないかを三項演算子で判定し、端であれば長さを1から再カウントします。
• 計算量： 行列の全セルを一度だけ走査するため、時間計算量は O(rows × cols) となり、大規模な行列でも高速に動作します。

出力結果

このコードを実行すると、コンソールには以下の出力が表示されます。

3

これは、arr[0][1] から arr[2][3] へと斜め方向に続く3つの1が、行列内で最長のラインであることを示しています。