글 읽기 - 숫자 정사각형 푸신분들께 질문 있습니다.

jjwdi0 7년 전 0

이 문제를 다이나믹으로 접근해서

DT[x][y]를 (0, 0)부터 (x, y)까지의 가장 큰 정사각형

이렇게 정의하고

DT[x][y]=max( f(x-1, y) , f(x, y-1) )

이렇게 하고 또 (x, y)로 만들 수 있는 큰 정사각형이랑 값을 비교하면서 구했는데

혹시 밑의 소스코드에 대한 반례가 있나요?ㅠㅠ

아니면 제 점화식이 잘못된 것인지...

#include <stdio.h>
int a[53][53], DT[53][53], n, m, i, j;
int min(int x, int y)
{
	return x>y?y:x;
}
int max(int x, int y)
{
	return x>y?x:y;
}
int f(int x, int y)
{
	if(DT[x][y])return DT[x][y];
	if(x*y==0)return DT[x][y]=1;
	DT[x][y]=max(f(x-1, y), f(x, y-1));
	for(int p=0; p<min(x, y); p++)
	{
		if(a[x-min(x, y)+p][y]==a[x-min(x, y)+p][y-min(x, y)+p] && a[x-min(x, y)+p][y-min(x, y)+p]==a[x][y] && a[x][y-p]==a[x][y] && (min(x, y)-p+1)*(min(x, y)-p+1)>DT[x][y])
		{
//			printf("%d %d %d\n", x, y, p);
			DT[x][y]=(min(x, y)-p+1)*(min(x, y)-p+1);
			break;
		}
	}
	return DT[x][y];
}
main()
{
	scanf("%d %d", &n, &m);
	for(i=0; i<n; i++)
		for(j=0; j<m; j++)
		scanf("%1d", &a[i][j]);
	printf("%d", f(n-1, m-1));
}

zzapCoder 7년 전 0

4 4
1234
1234
1255
1255

하면 1이 나옵니다

jjwdi0 7년 전 0

풀었습니다. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

숫자 정사각형 푸신분들께 질문 있습니다.

jjwdi0 7년 전 0

zzapCoder 7년 전 0

jjwdi0 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말