글 읽기 - 반례 케이스를 찾고 싶습니다 (주석 있음)

rail 3년 전 0

제가 혼자 힘으로 풀어보려다 도저히 안돼서

코드플러스 강의를 통해 받은 정답 코드를 봤습니다.

제 코드보다 짧고 간결했지만 원리상으로는 같아 보였는데

어떤 반례 케이스 때문에 차이가 생기는지 도저히 모르겠습니다....

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

struct coin {
	int x;
	int y;
};

int n, m;
char** arr;
coin c1, c2;

bool drop(coin a) {
	if (a.x < 0 || a.x >= n)return 1;
	else if (a.y < 0 || a.y >= m)return 1;
	else return 0;
}
// a라는 동전이 떨어졌는지 여부

void coinCopy(coin* a, coin b) {
	a->x = b.x;
	a->y = b.y;
}
// 동전 a의 위치를 b로 설정

void move(coin a, coin b) {
	arr[c1.x][c1.y] = '.';
	arr[c2.x][c2.y] = '.';

	if (arr[a.x][a.y] == '#')arr[c1.x][c1.y] = 'o';
	else {
		arr[a.x][a.y] = 'o';
		c1.x = a.x;
		c1.y = a.y;
	}

	if (arr[b.x][b.y] == '#')arr[c2.x][c2.y] = 'o';
	else {
		arr[b.x][b.y] = 'o';
		c2.x = b.x;
		c2.y = b.y;
	}
}
// c1,c2를 각각 a,b의 위치로 이동

int calc(int depth);

int main() {
	c1.x = -1;

	scanf("%d %d", &n, &m);
	getchar();
	arr = new char* [n];

	for (int i = 0; i < n; i++) {
		arr[i] = new char[m];

		for (int j = 0; j < m; j++) {
			scanf("%c", &arr[i][j]);
			if (arr[i][j] == 'o') {
				if (c1.x == -1) {
					c1.x = i;
					c1.y = j;
				}
				else {
					c2.x = i;
					c2.y = j;
				}
			}
		}
		getchar();
	}

	printf("%d", calc(0));

	return 0;
}

int calc(int depth) {
	if (depth > 10)return -1;
	// 10회 초과
	if (c1.x == c2.x && c1.y == c2.y)return -1;
	// 동전이 겹치면 하나만 떨어뜨릴 수 없음

	coin n1, n2;
	
	int xw[4] = { 1,0,-1,0 };
	int yw[4] = { 0,1,0,-1 };


	int minN = -1;
	for (int i = 0; i < 4; i++) {
		int res;

		n1.x = c1.x + xw[i];
		n1.y = c1.y + yw[i];
		n2.x = c2.x + xw[i];
		n2.y = c2.y + yw[i];
		
		if (drop(n1) || drop(n2)) { // 떨어진 동전이 있음
			if (drop(n1) && drop(n2))continue;
			else res = depth + 1;
		} 
		else if (arr[n1.x][n1.y] == arr[n2.x][n2.y]) { // 두 동전 이동이 모두 막혔거나 모두 뚫림
			if (arr[n1.x][n1.y] == '#')continue;
			else {
				coin ori1, ori2;
				coinCopy(&ori1, c1);
				coinCopy(&ori2, c2);

				move(n1, n2);
				res = calc(depth + 1);

				coinCopy(&c1, ori1);
				coinCopy(&c2, ori2);

				arr[n1.x][n1.y] = '.';
				arr[n2.x][n2.y] = '.';
				arr[c1.x][c1.y] = 'o';
				arr[c2.x][c2.y] = 'o';
			}
		} 
		else { // 두 동전 중 하나만 벽으로 막힘
			if (arr[n1.x][n1.y] == '#') {
				coin ori1, ori2;
				coinCopy(&ori1, c1);
				coinCopy(&ori2, c2);

				move(n1, n2);
				res = calc(depth + 1);

				coinCopy(&c1, ori1);
				coinCopy(&c2, ori2);

				arr[n2.x][n2.y] = '.';
				arr[c1.x][c1.y] = 'o';
				arr[c2.x][c2.y] = 'o';
			}
			else {
				coin ori1, ori2;
				coinCopy(&ori1, c1);
				coinCopy(&ori2, c2);

				move(n1, n2);
				res = calc(depth + 1);

				coinCopy(&c1, ori1);
				coinCopy(&c2, ori2);

				arr[n1.x][n1.y] = '.';
				arr[c1.x][c1.y] = 'o';
				arr[c2.x][c2.y] = 'o';
			}
		}

		if (res == -1)continue;
		else if (minN == -1 || minN > res)minN = res;
	}

	return minN;
}

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

문제

문제

출처

ICPC

반례 케이스를 찾고 싶습니다 (주석 있음)

rail 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말