Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 합이 k와 같은 가장 큰 면적의 직사각형 부분행렬 찾기


2D 행렬 매트와 값 K가 있다고 가정하면 합이 K와 같은 가장 긴 직사각형 부분행렬을 찾아야 합니다.

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

2 8 -5 6
-7 7 8 -3
11 -14 4 3
-4 3 1 10

K =9

그러면 출력은 왼쪽 위 지점이 (1, 0)이고 오른쪽 아래 지점이 (3, 2)입니다.

-7 7 8
11 -14 4
-4 3 1

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

  • 최대 :=100

  • sum_k() 함수를 정의하면 하나의 배열 arr, start, end, n, k,

    가 필요합니다.
  • 하나의 지도 정의

  • 합계 :=0, 최대 길이 :=0

  • initialize i :=0의 경우, i

    • 합계 :=합계 + arr[i]

    • 합계가 k와 같으면 -

      • 최대 길이 :=i + 1

      • 시작 :=0

      • 끝 :=나는

    • 합계가 맵에 없으면 -

      • 지도[합] :=i

    • (합 - k)가 맵에 있으면 -

      • maximum_length <(i - map[sum - k])이면 -

        • maximum_length :=i - map[sum - k]

        • 시작 :=맵[합 - k] + 1

        • 끝 :=나는

  • maximum_length가 0이 아니면 true를 반환

  • 기본 방법에서 다음을 수행하십시오 -

  • row :=매트의 행 개수, col :=매트의 열 개수

  • row.

    크기의 배열 온도를 정의합니다.
  • 배열을 정의합니다. final_point ={0,0,0,0}

  • maxArea :=-inf

  • 왼쪽 초기화의 경우:=0, 왼쪽 <열일 때 업데이트(왼쪽으로 1 증가), −

    • 온도를 0으로 채우기

    • for initialize right :=left, right

      • initialize i :=0의 경우 i

        • temp[i] :=temp[i] + mat[i, right]

      • 합계 :=sum_k(온도, 위, 아래, 행, k)

      • 면적 :=(아래 - 위 + 1) * (오른쪽 - 왼쪽 + 1)

      • 합계가 0이 아니고 maxArea <면적이면 -

        • final_point[0] :=위로, final_point[1] :=아래로

        • final_point[2] :=왼쪽, final_point[3] :=오른쪽

        • maxArea :=면적

    • final_point가 [0,0,0,0]이고 mat[0,0]이 k가 아니면

      • "하위 행렬을 찾을 수 없음"을 반환합니다.

  • 왼쪽 상단 포인트 표시(final_point[0], final_point[2])

  • 오른쪽 하단 포인트 표시(final_point[1], final_point[3])

  • 디스플레이 매트 요소.

예시

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

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
bool sum_k(int arr[], int& start, int& end, int n, int k) {
   unordered_map<int, int> map;
   int sum = 0, maximum_length = 0;
   for (int i = 0; i < n; i++) {
      sum += arr[i];
      if (sum == k) {
         maximum_length = i + 1;
         start = 0;
         end = i;
      }
      if (map.find(sum) == map.end())
         map[sum] = i;
      if (map.find(sum - k) != map.end()) {
         if (maximum_length < (i - map[sum - k])) {
            maximum_length = i - map[sum - k];
            start = map[sum - k] + 1;
            end = i;
         }
      }
   }
   return (maximum_length != 0);
}
void sum_zero(vector<vector<int>> &mat, int k) {
   int row = mat.size();
   int col = mat[0].size();
   int temp[row], area;
   bool sum;
   int up, down;
   vector<int> final_point = {0,0,0,0};
   int maxArea = INT_MIN;
   for (int left = 0; left < col; left++) {
      memset(temp, 0, sizeof(temp));
      for (int right = left; right < col; right++) {
         for (int i = 0; i < row; i++)
            temp[i] += mat[i][right];
         sum = sum_k(temp, up, down, row, k);
         area = (down - up + 1) * (right - left + 1);
         if (sum && maxArea < area) {
            final_point[0] = up;
            final_point[1] = down;
            final_point[2] = left;
            final_point[3] = right;
            maxArea = area;
         }
      }
   }
   if (final_point[0] == 0 && final_point[1] == 0 && final_point[2] == 0 &&
   final_point[3] == 0 && mat[0][0] != k) {
      cout << "No sub-matrix found";
      return;
   }
   cout << "(Top, Left) Coordinate: " << "(" << final_point[0] << ", " << final_point[2] << ")" << endl;
   cout << "(Bottom, Right) Coordinate: " << "(" << final_point[1] << ", " << final_point[3] << ")" << endl;
   for (int j = final_point[0]; j <= final_point[1]; j++) {
      for (int i = final_point[2]; i <= final_point[3]; i++)
         cout << mat[j][i] << " ";
      cout << endl;
   }
}
main(){
   vector<vector<int>> v = {
      { 2, 8, -5, 6 },
      { -7, 7, 8, -3 },
      { 11, -14, 4, 3 },
      { -4, 3, 1, 10 }};
   sum_zero(v, 9);
}

입력

{{ 2, 8, -5, 6 },
{ -7, 7, 8, -3 },
{ 11, -14, 4, 3 },
{ -4, 3, 1, 10 }},
9

출력

(Top, Left) Coordinate: (1, 0)
(Bottom, Right) Coordinate: (3, 2)
-7 7 8
11 -14 4
-4 3 1