글 읽기 - 반례를 못찾겠어요...

smtsyh 7년 전 0

좌표값으로 회전횟수 계산해서 하는 방법인데 반례를 못찾겠습니다...ㅠ

문제가 있는 방법인가요?

#include <stdio.h>

#define ABS(a) a < 0 ? (-a) : a

using namespace std;


int origin[17][2];
int input[5][5];
int cnt[8][8][2];
enum {V, H};
int result[7][3];
int total_cnt;

int moveCnt(int ori, int cur);
int min4(int a, int b, int c, int d);
void calc(int cur, int type, int move);

int main(void)
{
	//각 번호의 원래 위치 저장
	int temp = 1;
	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			origin[temp][0] = i;
			origin[temp][1] = j;
			temp++;
		}
	}

	temp = 1;
	for (int i = 1; i <= 4; i++)
	{
		for (int j = 1; j <= 4; j++)
		{
			scanf("%d", &input[i][j]);
			if (temp != input[i][j])
			{
				int ori_row = origin[input[i][j]][0];
				int ori_col = origin[input[i][j]][1];
				cnt[i][j][V] = moveCnt(ori_row, i);
				cnt[i][j][H] = moveCnt(ori_col, j);
			}
			temp++;
		}
	}

	int check = 1;
	while (check)
	{
		int move;
		check = 0;
		for (int i = 1; i <= 4; i++)
		{
			if (cnt[i][1][H] && cnt[i][2][H] && cnt[i][3][H] && cnt[i][4][H])
			{
				check = 1;
				move = min4(cnt[i][1][H], cnt[i][2][H], cnt[i][3][H], cnt[i][4][H]);
				calc(i, H, move);
				result[total_cnt][0] = 1;
				result[total_cnt][1] = i;
				result[total_cnt][2] = move;
				total_cnt++;
			}
		}

		for (int i = 1; i <= 4; i++)
		{
			if (cnt[1][i][V] && cnt[2][i][V] && cnt[3][i][V] && cnt[4][i][V])
			{
				check = 1;
				move = min4(cnt[1][i][V], cnt[2][i][V], cnt[3][i][V], cnt[4][i][V]);
				calc(i, V, move);
				result[total_cnt][0] = 2;
				result[total_cnt][1] = i;
				result[total_cnt][2] = move;
				total_cnt++;
			}
		}
	}

	printf("%d\n", total_cnt);
	for (int i = 0; i < total_cnt; i++)
		printf("%d %d %d\n", result[i][0], result[i][1], result[i][2]);

	return 0;
}

int moveCnt(int ori, int cur)
{
	int ret;
	if (ori == cur)
		return 0;
	else if (cur > ori)
		return (4 + ori - cur);
	else
		return ori - cur;
}

int min4(int a, int b, int c, int d)
{
	int ret = a;
	if (ret > b)
		ret = b;
	if (ret > c)
		ret = c;
	if (ret > d)
		ret = d;
	return ret;
}

void calc(int cur, int type, int move)
{
	int index = 4 + move;
	if (type == H)
	{
		for (int i = 4; i >= 1; i--)
		{
			cnt[cur][index][H] = cnt[cur][i][H];
			cnt[cur][index][V] = cnt[cur][i][V];
			cnt[cur][index][H] -= move;
			index--;
		}
		for (int i = 1; i <= move; i++)
		{
			cnt[cur][i][H] = cnt[cur][4 + i][H];
			cnt[cur][i][V] = cnt[cur][4 + i][V];
		}
	}
	else
	{
		for (int i = 4; i >= 1; i--)
		{
			cnt[index][cur][V] = cnt[i][cur][V];
			cnt[index][cur][H] = cnt[i][cur][H];
			cnt[index][cur][V] -= move;
			index--;
		}
		for (int i = 1; i <= move; i++)
		{
			cnt[i][cur][V] = cnt[4 + i][cur][V];
			cnt[i][cur][H] = cnt[4 + i][cur][H];
		}
	}
}

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

문제

문제

출처

ICPC

반례를 못찾겠어요...

smtsyh 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말