글 읽기 - 21% 에서 틀렸습니다 도와주세요ㅠ

swrho 4년 전 0

질문 게시판에 있는 모든 예제가 통과가 됩니다 반례를 찾기 함드네요,,ㅠ

일단 저는 구조체로 R 과 B 의 x y 좌표 d (이동 거리) prev(이전에 상하좌우중 무엇으로 움직였는지)

를 저장했고요

184번째 줄에서 부터는 그전의 prev 에서 1 (y 좌표로 -1방향으로 이동했다면)

y좌표로 +1 방향으로 이동하는것은 생각해볼 필요가 없기 때문에 if (d == 0 && Q[ed].prev != 1) 이런식으로

로 해뒀습니다

131번째 줄부터는 R 과 B 의 xy 좌표를 비교한 다음 R 을 먼저 이동 할것인지 B를 먼저 이동할 것인지 정하는 것입니다

해결해 주시면 감사하겠습니다

#include<stdio.h>
#include<stdlib.h>
void copyMap(char copy[][12], char orig[][12]);
typedef struct Queue {
	char map[12][12];
	int d, prev = -1;
	int Rx, Ry, Bx, By;
}queue;
queue Q[1050000]; // -> 4 pow 10 을 염두해둔것
queue temp;
int N, M, st, ed = -1, dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
char map[12][12];
int Rflag, Bflag;
void Rfirst(int d) {
	int Rflag = 0, Bflag = 0;
	while (1) { // R 부터 이동
		if (temp.map[temp.Rx + dx[d]][temp.Ry + dy[d]] == '.') {
			temp.map[temp.Rx + dx[d]][temp.Ry + dy[d]] = 'R';
			temp.map[temp.Rx][temp.Ry] = '.';
			temp.Rx += dx[d], temp.Ry += dy[d];
		}
		else if (temp.map[temp.Rx + dx[d]][temp.Ry + dy[d]] == '#') break;
		else if (temp.map[temp.Rx + dx[d]][temp.Ry + dy[d]] == 'O') {
			Rflag = 1;
			temp.map[temp.Rx][temp.Ry] = '.';
			break;
		}
		else {
			temp.map[temp.Rx + dx[d]][temp.Ry + dy[d]] = '.';
			break;
		}
	}
	while (1) { //  B 이동
		if (temp.map[temp.Bx + dx[d]][temp.By + dy[d]] == '.') {
			temp.map[temp.Bx + dx[d]][temp.By + dy[d]] = 'B';
			temp.map[temp.Bx][temp.By] = '.';
			temp.Bx += dx[d], temp.By += dy[d];
		}
		else if (temp.map[temp.Bx + dx[d]][temp.By + dy[d]] == '#') break;
		else if (temp.map[temp.Bx + dx[d]][temp.By + dy[d]] == 'O') {
			Bflag = 1;
			temp.map[temp.Rx][temp.Ry] = '.';
			break;
		}
		else {
			break;
		}
	}
	if (Rflag && !Bflag) // R 만 구멍에 도달
	{
		printf("1");
		exit(0);
	}
	if (Bflag && !Rflag) {// B 만 구멍에 도달
		st--;
	}
	if (Rflag && Bflag) {// R B 둘다 구멍에 도달
		printf("0");
		exit(0);
	}
	if (!Rflag && !Bflag) // nothing into the hole
	{
		copyMap(Q[st].map, temp.map);
		Q[st].Rx = temp.Rx, Q[st].Ry = temp.Ry;
		Q[st].Bx = temp.Bx, Q[st].By = temp.By;
		Q[st].prev = d, Q[st].d = temp.d + 1;
	}
}
void Bfirst(int d) {
	int Rflag = 0, Bflag = 0;
	while (1) { //  B 이동
		if (temp.map[temp.Bx + dx[d]][temp.By + dy[d]] == '.') {
			temp.map[temp.Bx + dx[d]][temp.By + dy[d]] = 'B';
			temp.map[temp.Bx][temp.By] = '.';
			temp.Bx += dx[d], temp.By += dy[d];
		}
		else if (temp.map[temp.Bx + dx[d]][temp.By + dy[d]] == '#') break;
		else if (temp.map[temp.Bx + dx[d]][temp.By + dy[d]] == 'O') {
			Bflag = 1;
			temp.map[temp.Rx][temp.Ry] = '.';
			break;
		}
		else {
			break;
		}
	}
	while (1) { // R 부터 이동
		if (temp.map[temp.Rx + dx[d]][temp.Ry + dy[d]] == '.') {
			temp.map[temp.Rx + dx[d]][temp.Ry + dy[d]] = 'R';
			temp.map[temp.Rx][temp.Ry] = '.';
			temp.Rx += dx[d], temp.Ry += dy[d];
		}
		else if (temp.map[temp.Rx + dx[d]][temp.Ry + dy[d]] == '#') break;
		else if (temp.map[temp.Rx + dx[d]][temp.Ry + dy[d]] == 'O') {
			Rflag = 1;
			temp.map[temp.Rx][temp.Ry] = '.';
			break;
		}
		else {
			break;
		}
	}
	if (Rflag && !Bflag) // R 만 구멍에 도달
	{
		printf("1");
		exit(0);
	}
	if (Bflag && !Rflag) {// B 만 구멍에 도달
		st--;
	}
	if (Rflag && Bflag) {// R B 둘다 구멍에 도달
		printf("0");
		exit(0);
	}
	if (!Rflag && !Bflag) // nothing into the hole
	{
		copyMap(Q[st].map, temp.map);
		Q[st].Rx = temp.Rx, Q[st].Ry = temp.Ry;
		Q[st].Bx = temp.Bx, Q[st].By = temp.By;
		Q[st].prev = d, Q[st].d = temp.d + 1;
	}

}
void move(int d) {
	int Rflag = 0, Bflag = 0;
	temp.Rx = Q[ed].Rx, temp.Ry = Q[ed].Ry;
	temp.Bx = Q[ed].Bx, temp.By = Q[ed].By;
	temp.d = Q[ed].d;

	if (d == 0) {
		if (temp.Ry > temp.By) {
			Rfirst(d);
		}
		else {
			Bfirst(d);
		}
	}
	else if (d == 1) {
		if (temp.Ry < temp.By) {
			Rfirst(d);
		}
		else {
			Bfirst(d);
		}
	}
	else if (d == 2) {
		if (temp.Rx > temp.Bx) {
			Rfirst(d);
		}
		else {
			Bfirst(d);
		}
	}
	else if (d == 3) {
		if (temp.Ry < temp.By) {
			Rfirst(d);
		}
		else {
			Bfirst(d);
		}
	}
	else
		;

}
void copyMap(char copy[][12], char orig[][12]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			copy[i][j] = orig[i][j];
		}
	}
}
void BFS(void) {
	copyMap(Q[0].map, map);
	Q[0].d = 0;
	while (st != ed) {
		ed++;
		if (Q[ed].d == 10) {
			printf("0");
			exit(0);
		}
		for (int d = 0; d < 4; d++) {
			copyMap(temp.map, Q[ed].map);
			if (d == 0 && Q[ed].prev != 1) {
				st++;
				move(d);
			}
			else if (d == 1 && Q[ed].prev != 0) {
				st++;
				move(d);
			}
			else if (d == 2 && Q[ed].prev != 3) {
				st++;
				move(d);
			}
			else if (d == 3 && Q[ed].prev != 2) {
				st++;
				move(d);
			}
			else
				;
		}
	}
}
int main() {
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf(" %1c", &map[i][j]);
			if (map[i][j] == 'R') Q[0].Rx = i, Q[0].Ry = j;
			if (map[i][j] == 'B') Q[0].Bx = i, Q[0].By = j;
		}
	}
	BFS();
}

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

문제

문제

출처

ICPC

21% 에서 틀렸습니다 도와주세요ㅠ

swrho 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말