C++의 행렬에서 가장 긴 연속 행

하나의 이진 행렬 M이 있다고 가정하면 해당 행렬에서 연속 행렬 중 가장 긴 줄을 찾아야 합니다. 선은 수평, 수직, 대각선 또는 역대각선일 수 있습니다.

따라서 입력이 다음과 같으면

그러면 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ret :=0

• n :=M의 행

• m :=M의 열

• n x m x 4 차수의 3D 배열 dp 하나를 정의합니다.

• initialize i :=0의 경우, i

  • j 초기화의 경우:=0, j <4일 때 업데이트(j를 1만큼 증가), 수행 -

    • dp[0, i, j] :=M[0, i]

    • ret :=ret 및 dp[0, i, j]의 최대값

• j 초기화의 경우:=0, j

  • M[0, j]가 0이 아니고 j> 0이면 -

    • dp[0, j, 1] :=1 + dp[0, j - 1, 1]

    • ret :=ret 및 dp[0, j, 1]의 최대값

• initialize i :=1의 경우, i

  • j 초기화의 경우:=0, j

    • dp[i, j, 0] :=(M[i, j]가 0이 아니면 1 + dp[i - 1, j, 0]이고 그렇지 않으면 0)

    • j> 0이면 -

      • dp[i, j, 1] :=(M[i, j]가 0이 아니면 dp[i, j - 1, 1] + 1, 그렇지 않으면 0)

      • dp[i, j, 2] :=(M[i, j]가 0이 아니면 dp[i - 1, j - 1, 2] + 1, 그렇지 않으면 0)

    • 그렇지 않으면

      • dp[i, j, 1] :=M[i, j]

      • dp[i, j, 2] :=M[i, j]

    • j + 1

      • dp[i, j, 3] :=(M[i, j]가 0이 아니면 dp[i - 1, j + 1, 3] + 1, 그렇지 않으면 0)

    • 그렇지 않으면

      • dp[i, j, 3] :=M[i, j]

    • 초기화 k :=0의 경우 k <4일 때 업데이트(k를 1만큼 증가), −

      • ret :=ret 및 dp[i, j, k]

        의 최대값

• 리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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();
      vector<vector<vector<int> > > dp(n, vector<vector<int> >(m, vector<int>(4)));
      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]);
         }
      }
      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]);
         }
      }
      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