스캐닝 라인 법 최대 서브 매트릭스 구하 기

2115 단어 학습 자료DP
질문 설명:
N * M 의 행렬 을 지정 합 니 다. 그 중 일 부 는 공 터 이 고 다른 것 은 장애 입 니 다.
모두 공 터 로 구 성 된 면적 / 둘레 가 가장 큰 서브 행렬 을 찾 아 라.
소박 한 알고리즘:
왼쪽 상단 의 좌표 O (mn) 와 오른쪽 하단 의 좌표 O (mn) 를 매 거 하여 모두 공 터 O (mn) 인지, 시간 복잡 도 는 O (m3 * n3) 인지 판단 한다.
스 캔 라인:
점 (i, j) 을 위 에 있 는 모든 연속 적 인 빈 칸 을 현 선 으로 본다.행렬 의 모든 점 이 위로 현 선 에 대응 했다.
① h [i, j] 로 점 (i, j) 에 대응 하 는 현 선 길 이 를 나타 낸다.
(i, j) 가 장애 일 때 h [i, j] = 0;(i, j) 가 빈 칸 일 때 h [i, j] = h [i - 1, j] + 1.
② left [i, j] 로 점 (i, j) 에 대응 하 는 현 선의 왼쪽 경 계 를 표시 합 니 다.
(i, j) 가 장애 일 때 left [i, j] = 왼쪽 경계;(i, j) 가 빈 칸 일 때, left [i, j] = max (left [i - 1, j], lo + 1), lo 는 칸 (i, j) 왼쪽 에서 가장 가 까 운 장애물 의 열 번호 입 니 다.
③ right [i, t] 로 점 (i, j) 에 대응 하 는 현 선의 오른쪽 경 계 를 표시 한다.
(i, j) 가 장애 일 때 right [i, j] = 오른쪽 경계;(i, j) 가 빈 칸 일 때 right [i, j] = min (right [i + 1, j], ro - 1), ro 는 칸 (i, j) 오른쪽 에서 가장 가 까 운 장애물 의 열 번호 입 니 다.
위 에서 아래로 스 캔 하고 모든 줄 을 왼쪽 에서 오른쪽으로 left [i, j] 유지 보수 lo 를 계산 합 니 다.오른쪽 에서 왼쪽으로 right [i, j] 를 계산 하여 ro 를 유지 하고 답 을 업데이트 합 니 다.
실제 실현 에서 공간 을 절약 하고 h [j], left [j], right [j] 로 현재 스 캔 줄 의 정 보 를 표시 합 니 다.
템 플 릿:
#include 
#include 
#include 
#include 

using namespace std;

const int maxn=1111;

int mat[maxn][maxn];
int n,m;

//         ,      c
int cat(int c)
{
    int h[maxn],l[maxn],r[maxn];
    int lo,ro;
    int ans=0;
    for (int j=1;j<=m;j++)
    {
        h[j]=0;
        l[j]=1;
        r[j]=m;
    }
    for (int i=1;i<=n;i++)
    {
        lo=0;ro=m+1;
        for (int j=1;j<=m;j++)
        {
            if (mat[i][j]==c){ h[j]=0;l[j]=1;lo=j; }
            else
            {
                h[j]++;
                l[j]=max(l[j],lo+1);
            }
        }
        for (int j=m;j>=1;j--)
        {
            if (mat[i][j]==c){ r[j]=m;ro=j; }
            else
            {
                r[j]=min(r[j],ro-1);
                ans=max(ans,h[j]*(r[j]-l[j]+1));
            }
        }
    }
    return ans;
}

제목:
UVa 1330 - 시 티 게임 최대 서브 매트릭스
hdu 4328 Cut the cake 최대 자 행렬

좋은 웹페이지 즐겨찾기