글 읽기 - 반례를 알고싶어요

kdr06006 5년 전 0

반례를 도저히 못찾겠습니다

#include<stdio.h>

int N, M, max, index;
int map[11][11];

typedef struct kang {
	int n;
	int x;
	int y;
}kk;
kk cc[11];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void TV(int c_index, int c)
{
	if (c_index == index) return;

	int tempmap[9][9];
	for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) tempmap[i][j] = map[i][j];
	int C = c;

	if (cc[c_index].n == 1)
	{
		for (int i = 0;i < 4;i++)
		{
			for (int a = 1;;a++)
			{
				int X = cc[c_index].x + dx[i] * a, Y = cc[c_index].y + dy[i] * a;
				if (X < 0 || X >= N || Y < 0 || Y >= M) break;

				if (map[X][Y] == 6) break;
				else if (map[X][Y] == 0)
				{
					map[X][Y] = -1;
					c++;
				}
			}
			if (c > max) max = c;
			TV(c_index + 1, c);
			for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) map[i][j] = tempmap[i][j];
			c = C;
		}
	}
	else if (cc[c_index].n == 2)
	{
		for (int i = 0;i < 2;i++)
		{
			for (int a = 1;;a++)
			{
				int X = cc[c_index].x + dx[i] * a, Y = cc[c_index].y + dy[i] * a;
				if (X < 0 || X >= N || Y < 0 || Y >= M) break;

				if (map[X][Y] == 6) break;
				else if (map[X][Y] == 0)
				{
					map[X][Y] = -1;
					c++;
				}
			}
		}
		if (c > max) max = c;
		TV(c_index + 1, c);
		for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) map[i][j] = tempmap[i][j];
		c = C;

		for (int i = 2;i < 4;i++)
		{
			for (int a = 1;;a++)
			{
				int X = cc[c_index].x + dx[i] * a, Y = cc[c_index].y + dy[i] * a;
				if (X < 0 || X >= N || Y < 0 || Y >= M) break;

				if (map[X][Y] == 6) break;
				else if (map[X][Y] == 0)
				{
					map[X][Y] = -1;
					c++;
				}
			}
		}
		if (c > max) max = c;
		TV(c_index + 1, c);
		for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) map[i][j] = tempmap[i][j];
		c = C;
	}
	else if (cc[c_index].n == 3)
	{
		for (int i = 0;i < 4;i += 2)
		{
			for (int a = 1;;a++)
			{
				int X = cc[c_index].x + dx[i] * a, Y = cc[c_index].y + dy[i] * a;
				if (X < 0 || X >= N || Y < 0 || Y >= M) break;

				if (map[X][Y] == 6) break;
				else if (map[X][Y] == 0)
				{
					map[X][Y] = -1;
					c++;
				}
			}
		}
		if (c > max) max = c;
		TV(c_index + 1, c);
		for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) map[i][j] = tempmap[i][j];
		c = C;

		for (int i = 0;i < 4;i += 3)
		{
			for (int a = 1;;a++)
			{
				int X = cc[c_index].x + dx[i] * a, Y = cc[c_index].y + dy[i] * a;
				if (X < 0 || X >= N || Y < 0 || Y >= M) break;

				if (map[X][Y] == 6) break;
				else if (map[X][Y] == 0)
				{
					map[X][Y] = -1;
					c++;
				}
			}
		}
		if (c > max) max = c;
		TV(c_index + 1, c);
		for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) map[i][j] = tempmap[i][j];
		c = C;

		for (int i = 1;i < 4;i++)
		{
			for (int a = 1;;a++)
			{
				int X = cc[c_index].x + dx[i] * a, Y = cc[c_index].y + dy[i] * a;
				if (X < 0 || X >= N || Y < 0 || Y >= M) break;

				if (map[X][Y] == 6) break;
				else if (map[X][Y] == 0)
				{
					map[X][Y] = -1;
					c++;
				}
			}
		}
		if (c > max) max = c;
		TV(c_index + 1, c);
		for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) map[i][j] = tempmap[i][j];
		c = C;

		for (int i = 1;i < 4;i += 2)
		{
			for (int a = 1;;a++)
			{
				int X = cc[c_index].x + dx[i] * a, Y = cc[c_index].y + dy[i] * a;
				if (X < 0 || X >= N || Y < 0 || Y >= M) break;

				if (map[X][Y] == 6) break;
				else if (map[X][Y] == 0)
				{
					map[X][Y] = -1;
					c++;
				}
			}
		}
		if (c > max) max = c;
		TV(c_index + 1, c);
		for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) map[i][j] = tempmap[i][j];
		c = C;
	}
	else if (cc[c_index].n == 4)
	{
		for (int i = 0;i < 4;i++)
		{
			for (int j = 0;j < 4;j++)
			{
				if (j == i) continue;
				for (int a = 1;;a++)
				{
					int X = cc[c_index].x + dx[j] * a, Y = cc[c_index].y + dy[j] * a;
					if (X < 0 || X >= N || Y < 0 || Y >= M) break;

					if (map[X][Y] == 6) break;
					else if (map[X][Y] == 0)
					{
						map[X][Y] = -1;
						c++;
					}
				}
			}
			if (c > max) max = c;
			TV(c_index + 1, c);
			for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) map[i][j] = tempmap[i][j];
			c = C;
		}
	}
	else
	{
		for (int i = 0;i < 4;i++)
		{
			for (int a = 1;;a++)
			{
				int X = cc[c_index].x + dx[i] * a, Y = cc[c_index].y + dy[i] * a;
				if (X < 0 || X >= N || Y < 0 || Y >= M) break;

				if (map[X][Y] == 6) break;
				else if (map[X][Y] == 0)
				{
					map[X][Y] = -1;
					c++;
				}
			}
		}
		if (c > max) max = c;
		TV(c_index + 1, c);
		c = C;
		for (int i = 0;i < N;i++) for (int j = 0;j < M;j++) map[i][j] = tempmap[i][j];
	}
}

int main(void)
{
	scanf("%d %d", &N, &M);
	int res = 0;
	for (int i = 0;i < N;i++)
	{
		for (int j = 0;j < M;j++)
		{
			scanf("%d", &map[i][j]);
			if (map[i][j] == 0) res++;
			else if (map[i][j] != 6) cc[index++] = { map[i][j],i,j };
		}
	}

	TV(0, 0);

	printf("%d\n", res - max);
}

dladydwo123 5년 전 1

cctv가 케이스 3번인 경우

for (int i = 1; i < 4; i++) {

...

}

이 부분의도가 i=1, i=2만 탐색하게 할려고 하신거 같은데 i=3도 도는거 같아요

kdr06006 5년 전 1

@dladydwo123

우와.. 감사합니다!! 덕분에 맞았어요~~

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

문제

문제

출처

ICPC

반례를 알고싶어요

kdr06006 5년 전 0

dladydwo123 5년 전 1

kdr06006 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말