C++でマトリックス内の連続する1の最長ラインを求める方法(動的計画法)

問題概要

0と1だけで構成されたバイナリ行列 M が与えられます。この行列の中から、連続した1が並ぶ最長のラインの長さを求めてください。ラインの向きは、水平方向・垂直方向・斜め(対角線)方向・反斜め(逆対角線)方向のいずれかです。

例として、次のような入力を考えてみましょう。

この場合の出力は 3 です。(0,1) → (1,2) → (2,3) と、左上から右下へ向かう対角線上に1が3つ連続して並んでいるためです。

解法アプローチ:動的計画法(DP)

この問題は、4つの方向それぞれについて「そのセルを終点とする連続する1の長さ」を記録する動的計画法で効率的に解くことができます。手順は以下の通りです。

• 答えを格納する変数 ret を 0 で初期化します。
• n に行列の行数、m に列数を設定します。
• n × m × 4 のサイズを持つ3次元配列 dp を定義します。dp[i][j][k] は、セル (i, j) を終点とする方向 k の連続する1の長さを表します。

インデックス k と方向の対応は次の通りです。

• k = 0: 垂直方向(上から下)
• k = 1: 水平方向(左から右)
• k = 2: 斜め方向(左上から右下)
• k = 3: 反斜め方向(右上から左下)

初期化(0行目の処理)

• i = 0 から m 未満までループし、すべての方向 j(0〜3)に対して dp[0][i][j] = M[0][i] と設定し、ret を最大値で更新します。
• 続けて0行目の水平方向を処理します。M[0][j] が1かつ j > 0 のとき、dp[0][j][1] = 1 + dp[0][j-1][1] として ret を更新します。

遷移(1行目以降の処理)

i = 1 から n 未満まで、j = 0 から m 未満までループしながら、次の遷移を行います。

• 垂直方向: M[i][j] が1なら dp[i][j][0] = 1 + dp[i-1][j][0]、それ以外は 0。
• 水平方向・斜め方向(j > 0 のとき):
  • M[i][j] が1なら dp[i][j][1] = dp[i][j-1][1] + 1(水平方向)、それ以外は 0。
  • M[i][j] が1なら dp[i][j][2] = dp[i-1][j-1][2] + 1(斜め方向)、それ以外は 0。
• j = 0 のときは、dp[i][j][1] と dp[i][j][2] を M[i][j] の値そのもので初期化します。
• 反斜め方向(j + 1 < m のとき): M[i][j] が1なら dp[i][j][3] = dp[i-1][j+1][3] + 1、それ以外は 0。j + 1 = m の場合は M[i][j] で初期化します。
• 各セルで4方向の値を確認し、最大値を ret に反映させます。

すべてのセルを走査し終えたら ret を返します。計算量は時間・空間ともに O(n × m) であり、全探索(O(n × m × min(n, m)))よりも大幅に効率的です。

C++実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestLine(vector<vector<int>>& M) {
      int ret = 0;
      int n = M.size();
      int m = !n ? 0 : M[0].size();
      // dp[i][j][k]: セル(i,j)を終点とする方向kの連続する1の長さ
      vector<vector<vector<int> > > dp(n, vector<vector<int> >(m, vector<int>(4)));
      // 0行目の初期化
      for (int i = 0; i < m; i++) {
         for (int j = 0; j < 4; j++) {
            dp[0][i][j] = M[0][i];
            ret = max(ret, dp[0][i][j]);
         }
      }
      // 0行目の水平方向を処理
      for (int j = 0; j < m; j++) {
         if (M[0][j] && j > 0) {
            dp[0][j][1] = 1 + dp[0][j - 1][1];
            ret = max(ret, dp[0][j][1]);
         }
      }
      // 1行目以降の遷移
      for (int i = 1; i < n; i++) {
         for (int j = 0; j < m; j++) {
            dp[i][j][0] = M[i][j] ? 1 + dp[i - 1][j][0] : 0;
            if (j > 0) {
               dp[i][j][1] = M[i][j] ? dp[i][j - 1][1] + 1 : 0;
               dp[i][j][2] = M[i][j] ? dp[i - 1][j - 1][2] + 1 : 0;
            }
            else {
               dp[i][j][1] = M[i][j];
               dp[i][j][2] = M[i][j];
            }
            if (j + 1 < m) {
               dp[i][j][3] = M[i][j] ? dp[i - 1][j + 1][3] + 1 : 0;
            }
            else {
               dp[i][j][3] = M[i][j];
            }
            for (int k = 0; k < 4; k++) {
               ret = max(ret, dp[i][j][k]);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,1,0},{0,1,1,0},{0,0,0,1}};
   cout << (ob.longestLine(v));
}

入力

{{0,1,1,0},{0,1,1,0},{0,0,0,1}}

出力

3