글 읽기 - 반례좀 찾아주세요 ㅠㅠ

danieljskang1011 3년 전 0

3%에서 자꾸 막히네요...아무리 예제 넣어봐도 모르겠네요.

#include <cstdio>

int n;
int data[2200][2200];

int a, b, c;

void solve(int x1, int x2, int y1, int y2)
{	
//	printf("%d %d %d %d\n",x1,x2,y1,y2);
	int i, j;
	bool what = true;
	int first = data[x1][y1]; 
	
	
	for(i=x1;i<=x2;i++) // 종이 한장인지 체크
	{
		for(j=y1;j<=y2;j++)
		{
			if(data[i][j] != first)
			{
				what = false;
				break;
			}
		}
		if(!what) break;
	}
	
	
	if(what) // 종이 한장이면 끝내기
	{
		if(first == -1) a++;
		else if(first == 0) b++;
		else c++;	
		return;
	}
	else
	{
		int dx = (x2 - x1 + 1) / 3; 
		int dy = (y2 - y1 + 1) / 3;
		
		solve(x1,x1+dx-1,y1,y1+dy-1);
		solve(x1,x1+dx-1,y1+dy,y1+dy*2-1);
		solve(x1,x1+dx-1,y1+dy*2,dy*3);
		
		solve(x1+dx,x1+dx*2-1,y1,y1+dy-1);
		solve(x1+dx,x1+dx*2-1,y1+dy,y1+dy*2-1);
		solve(x1+dx,x1+dx*2-1,y1+dy*2,dy*3);
		
	    solve(x1+dx*2,dx*3,y1,y1+dy-1);
		solve(x1+dx*2,dx*3,y1+dy,y1+dy*2-1);
		solve(x1+dx*2,dx*3,y1+dy*2,dy*3);
	    
		return;	
	}
}

int main()
{
	scanf("%d",&n);
	int i, j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			scanf("%d",&data[i][j]);
		}
	}
	solve(1,n,1,n);
	
	printf("%d\n%d\n%d",a,b,c);
}

hibye1217 3년 전 2

44, 48, 52번 줄의 4번째 매개변수 (y2)가 잘못되었습니다.
50, 51, 52번 줄의 2번째 매개변수 (x2)도 잘못되었습니다.

dy, dx는 (개수) / 3을 나타내기 때문에,
만약 x1 = 10, x2 = 18이었다면, dx = 9 / 3 = 3이 되고,
(x1 + dx × 2, dx × 3)은 (16, 9)가 됩니다.

반례로는 다음이 있습니다.

Input
27
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

WA (Output)
0
17
0

Answer
0
24
1

danieljskang1011 3년 전 0

감사합니다!

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

문제

문제

출처

ICPC

반례좀 찾아주세요 ㅠㅠ

danieljskang1011 3년 전 0

hibye1217 3년 전 2

danieljskang1011 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말