스캐닝 라인 법 최대 서브 매트릭스 구하 기
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 최대 자 행렬
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
스캐닝 라인 법 최대 서브 매트릭스 구하 기② left [i, j] 로 점 (i, j) 에 대응 하 는 현 선의 왼쪽 경 계 를 표시 합 니 다. (i, j) 가 장애 일 때 left [i, j] = 왼쪽 경계;(i, j) 가 빈 칸 일 때, left [i,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
