글 읽기 - 반례를 못찾겠습니다

njh7799 5년 전 0

블로그에 있던 100가지 케이스를 시도해 보았는데도 찾지 못했습니다ㅠ 혹시 도와주실 수 있으신가요?

#include<cstdio>
#include<queue>
using namespace std;

struct Point {
	int x;
	int y;
	bool operator== (Point &rhs) {
		return this->x == rhs.x && this->y == rhs.y;
	}
	bool operator!= (Point &rhs) {
		return !(this->x == rhs.x && this->y == rhs.y);
	}
};

struct RB {
	Point R;
	Point B;
};

int n, m;
char a[10][10];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1};
Point R, B, O;
int d[10] = { 0, };


// 매 시행마다 구슬을 굴리는 함수
//P가 처리할 구슬 P2가 다른 구슬, O가 탈출 점
Point roll(Point P, Point P2, Point O,  int dir) {
	while (1) {
		Point next = { P.x + dx[dir], P.y + dy[dir] };
		if (P == O) break;
		if (next == P2 && next != O) break;
		if (a[next.x][next.y] == '#') break;
		P = next;
	}
	return P;
}



int main() {
//	freopen("input.txt", "r", stdin);
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) scanf("%s", a[i]);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 'R') R = { i,j }, a[i][j]='.';
			else if (a[i][j] == 'B') B = { i,j }, a[i][j] = '.';
			else if (a[i][j] == 'O') O = { i,j }, a[i][j] = '.';
		}
	}


	queue<RB> q;
	q.push({ R, B });
	int ans = 11;

	//시간 t가 증가함에 따라 진행되도록 설정했습니다.
	for (int t = 0; t<ans; t++) {
		queue<RB> q2;

		while (!q.empty()) {
			RB crr = q.front();
			q.pop();
			if (crr.B == O) continue;// B가 O에 빠지는 경우는 실패이기 때문에 continue
			else if (crr.R == O) {// B가 안빠지고 R이 빠지는 경우 성공
				ans = t;
				break;
			}

			//
			for (int dir = 0; dir < 4; dir++) {

				// 구슬을 굴려줍니다. R 구슬과 B 구슬이 서로의 경로를 막으면 안되기 때문데 R, B, R 세번의 처리를 진행했습니다.
				Point tempR = roll(crr.R, crr.B, O, dir);
				Point tempB = roll(crr.B, tempR, O, dir);
				tempR = roll(tempR, tempB, O, dir);
				//


				if (crr.R == tempR && crr.B == tempB) continue;
				q2.push({ tempR, tempB });
			}
		}
		q = q2;
	}

	ans = ans == 11 ? -1 : ans;
	printf("%d", ans);
//	fclose(stdout);
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다

njh7799 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말