글 읽기 - 1915번 질문입니다.

wellshs 8년 전 0

아직까지도 해결을 하지 못해서 다시 여쭤봅니다...

res라는 배열을 결과를 저장하는 배열로 하여, res[i][j]는 input을 저장하는 arr[i][j]위치를 오른쪽 아래로 하는 정사각형중에 가장 큰 정사각형값을 가지는 것을 저장하였습니다.

그래서 res[i][j]를 구할때, arr[i][j]를 확인하여 1이면 res[i-1][j-1]의 값을 받아서 가장 오른쪽 벽과, 가장 아랫쪽 벽을 체크하여 다 1일 경우 +1을 하여 res[i][j]값에 저장하게 했습니다.

이런 구현이 잘못된건가요? 아니면 제코드에 실수가 있나요?

며칠째 해결이 되지 않아 답답합니다.... 도움 부탁드려요..

#include <stdio.h>
char arr[1010][1010];
int res[1010][1010];
int main(){
	int n,m, i, j,k, p, chk, max=0;
	scanf("%d %d", &n, &m);
	for(i=0;i<n;i++){
		scanf("%s", arr[i]);
	}
	for(i=0;i<n;i++){
		res[i][0] = arr[i][0]-48;
		if(arr[i][0]=='1')
			max=1;
	}
	for(i=1;i<m;i++){
		res[0][i] = arr[0][i]-48;
		if(arr[0][i]=='1')
			max=1;
	}
	for(i=1;i<m+n-1;i++){
		for(j=1;j<i;j++){
			if(j>=m || i-j>=n)
				continue;
			else{
				if(arr[i-j][j]=='0')
					res[i-j][j]=0;
				else{
					k = res[i-j-1][j-1];
					chk=0;
					for(p = 1;p<=k;p++){
						if(arr[i-j-p][j]=='0' || arr[i-j][j-p]=='0')
							chk=1;
					}
					if(chk==1){
						res[i-j][j] = 1;
						if(max<res[i-j][j])
							max = res[i-j][j];
					}
					else{
						res[i-j][j] = k+1;
						if(max<res[i-j][j])
							max = res[i-j][j];
					}
				}
			}
		}
	}
	printf("%d", max*max);
}

ntopia 8년 전 4

아래와 같은 데이터에서 잘못된 답이 나옵니다

wellshs 8년 전 0

아... 전혀 생각못했네요... 감사합니다!

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

문제

문제

출처

ICPC

1915번 질문입니다.

wellshs 8년 전 0

ntopia 8년 전 4

wellshs 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말