Computer >> Máy Tính >  >> Lập trình >> C ++

Dòng dài nhất của một liên tiếp trong ma trận trong C ++

Giả sử chúng ta có một ma trận nhị phân M, chúng ta phải tìm dòng dài nhất liên tiếp trong ma trận đó. Đường có thể nằm ngang, dọc, chéo hoặc chống chéo.

Vì vậy, nếu đầu vào giống như

0 1 1 0
0 1 1 0
0 0 0 1

thì đầu ra sẽ là 3

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • ret:=0

  • n:=hàng của M

  • m:=cột của M

  • Xác định một dp mảng 3D có thứ tự n x m x 4

  • để khởi tạo i:=0, khi i

    • để khởi tạo j:=0, khi j <4, cập nhật (tăng j lên 1), thực hiện -

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

      • ret:=tối đa ret và dp [0, i, j]

  • để khởi tạo j:=0, khi j

    • nếu M [0, j] khác 0 và j> 0, thì -

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

      • ret:=tối đa ret và dp [0, j, 1]

  • để khởi tạo i:=1, khi i

    • để khởi tạo j:=0, khi j

      • dp [i, j, 0]:=(nếu M [i, j] khác 0 thì 1 + dp [i - 1, j, 0], ngược lại là 0)

      • nếu j> 0, thì -

        • dp [i, j, 1]:=(nếu M [i, j] khác 0 thì dp [i, j - 1, 1] + 1, ngược lại là 0)

        • dp [i, j, 2]:=(nếu M [i, j] khác 0 thì dp [i - 1, j - 1, 2] + 1, nếu không thì 0)

      • Nếu không

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

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

      • nếu j + 1

        • dp [i, j, 3]:=(nếu M [i, j] khác 0 thì dp [i - 1, j + 1, 3] + 1, ngược lại là 0)

      • Nếu không

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

      • để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện -

        • ret:=tối đa ret và dp [i, j, k]

  • trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#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));
}

Đầu vào 

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

Đầu ra 

3