글 읽기 - 틀렸다고 뜨는데 제발 도와주세요ㅠㅠㅠ 주석처리했어요!

po00076 6년 전 0

컨셉은 Q를 만들어서 BFS로 했어요.

Left function에 주석을 달아 놨구요, right, up, down은 모두 left를 복사해서 한 것입니다.

올려주신 test case들 다 실행해봤는데 다 맞게 나오더라구요. 한 25%정도에서 틀리는데, 이유를 모르겠습니다..

도와주세요ㅠㅠ

#include <stdio.h>
#include <stdlib.h>

int N, M;
int map[20][10];
int holex;
int holey;
int Bin = 0;
int Rin = 0;

typedef struct _node
{
	int Bx;
	int By;
	int Rx;
	int Ry;
	int turn;
	_node * next;
}node;

typedef struct _queue
{
	node* qp;
	node* start;
	node* end;
}queue;

queue* init() {
	queue* a = (queue*)malloc(sizeof(queue));
	a->qp = a->start;
	a->start = NULL;
	a->end = NULL;

	return a;
}

node* newNode(int Bx, int By, int Rx, int Ry) {
	node* a = (node*)malloc(sizeof(node));
	a->Bx = Bx;
	a->By = By;
	a->Rx = Rx;
	a->Ry = Ry;
	a->next = NULL;
	a->turn = 0;

	return a;
}

queue* Q = init();

void left(node nd) {
	int bx = nd.Bx;
	int by = nd.By;
	int rx = nd.Rx;
	int ry = nd.Ry;

	//blue is on left of r when y is the same
	if (by == ry) {
		if (bx < rx) {
            //do the blue first
			while (bx > 0 && map[by][bx - 1] == 0) {
				bx--;
				if (bx == holex && by == holey) {
					Bin = 1;
					bx = -1;
					by = -1;
					break;
				}
			}
            //then red
			while (rx > bx + 1 && map[ry][rx - 1] == 0) {
				rx--;
				if (rx == holex && ry == holey) {
					Rin = 1;
					rx = -1;
					ry = -1;
					break;
				}
			}
		}
		else {
            //if red is on the left side of blue, do the red first
			while (rx > 0 && map[ry][rx - 1] == 0) {
				rx--;
				if (rx == holex && ry == holey) {
					Rin = 1;
					rx = -1;
					ry = -1;
					break;
				}
			}
            //if not, do the blue first
			while (bx > rx + 1 && map[by][bx - 1] == 0) {
				bx--;
				if (bx == holex && by == holey) {
					Bin = 1;
					bx = -1;
					by = -1;
					break;
				}
			}
		}
	}
	else {
        //if by and ry are not the same(blue and red are not on the same line), just do both.
		while (rx > 0 && map[ry][rx - 1] == 0) {
			rx--;
			if (rx == holex && ry == holey) {
				Rin = 1;
				rx = -1;
				ry = -1;
				break;
			}
		}
		while (bx > 0 && map[by][bx - 1] == 0) {
			bx--;
			if (bx == holex && by == holey) {
				Bin = 1;
				bx = -1;
				by = -1;
				break;
			}
		}
	}

	node* l = newNode(bx, by, rx, ry);
	l->turn = nd.turn + 1;

	Q->end->next = l;
	Q->end = Q->end->next;

}

void right(node nd) {
	int bx = nd.Bx;
	int by = nd.By;
	int rx = nd.Rx;
	int ry = nd.Ry;

	if (by == ry) {
		if (bx > rx) {
			while (bx < M && map[by][bx + 1] == 0) {
				bx++;
				if (bx == holex && by == holey) {
					Bin = 1;
					bx = -1;
					by = -1;
					break;
				}
			}
			while (rx < bx - 1 && map[ry][rx + 1] == 0) {
				rx++;
				if (rx == holex && ry == holey) {
					Rin = 1;
					rx = -1;
					ry = -1;
					break;
				}
			}
		}
		else {
			while (rx < M && map[ry][rx + 1] == 0) {
				rx++;
				if (rx == holex && ry == holey) {
					Rin = 1;
					rx = -1;
					ry = -1;
					break;
				}
			}
			while (bx < rx - 1 && map[by][bx + 1] == 0) {
				bx++;
				if (bx == holex && by == holey) {
					Bin = 1;
					bx = -1;
					by = -1;
					break;
				}
			}
		}
	}
	else {
		while (rx < M && map[ry][rx + 1] == 0) {
			rx++;
			if (rx == holex && ry == holey) {
				Rin = 1;
				rx = -1;
				ry = -1;
				break;
			}
		}
		while (bx < M && map[by][bx + 1] == 0) {
			bx++;
			if (bx == holex && by == holey) {
				Bin = 1;
				bx = -1;
				by = -1;
				break;
			}
		}
	}

	node* l = newNode(bx, by, rx, ry);
	l->turn = nd.turn + 1;

	Q->end->next = l;
	Q->end = Q->end->next;

}

void up(node nd) {
	int bx = nd.Bx;
	int by = nd.By;
	int rx = nd.Rx;
	int ry = nd.Ry;

	//blue is on left of r when y is the same
	if (bx == rx) {
		if (by < ry) {
			while (by > 0 && map[by - 1][bx] == 0) {
				by--;
				if (bx == holex && by == holey) {
					Bin = 1;
					bx = -1;
					by = -1;
					break;
				}
			}
			while (ry > by + 1&& map[ry - 1][rx] == 0) {
				ry--;
				if (rx == holex && ry == holey) {
					Rin = 1;
					rx = -1;
					ry = -1;
					break;
				}
			}
		}
		else {
			while (ry > 0 && map[ry - 1][rx] == 0) {
				ry--;
				if (rx == holex && ry == holey) {
					Rin = 1;
					rx = -1;
					ry = -1;
					break;
				}
			}
			while (by > ry + 1 && map[by - 1][bx] == 0) {
				by--;
				if (bx == holex && by == holey) {
					Bin = 1;
					bx = -1;
					by = -1;
					break;
				}
			}
		}
	}
	else {
		while (ry > 0 && map[ry - 1][rx] == 0) {
			ry--;
			if (rx == holex && ry == holey) {
				Rin = 1;
				rx = -1;
				ry = -1;
				break;
			}
		}
		while (by > 0 && map[by - 1][bx] == 0) {
			by--;
			if (bx == holex && by == holey) {
				Bin = 1;
				bx = -1;
				by = -1;
				break;
			}
		}
	}

	node* l = newNode(bx, by, rx, ry);
	l->turn = nd.turn + 1;

	Q->end->next = l;
	Q->end = Q->end->next;

}


void down(node nd) {
	int bx = nd.Bx;
	int by = nd.By;
	int rx = nd.Rx;
	int ry = nd.Ry;

	if (bx == rx) {
		if (by > ry) {
			while (by < M && map[by + 1][bx] == 0) {
				by++;
				if (bx == holex && by == holey) {
					Bin = 1;
					bx = -1;
					by = -1;
					break;
				}
			}
			while (ry < by - 1 && map[ry + 1][rx] == 0) {
				ry++;
				if (rx == holex && ry == holey) {
					Rin = 1;
					rx = -1;
					ry = -1;
					break;
				}
			}
		}
		else {
			while (ry < M && map[ry + 1][rx] == 0) {
				ry++;
				if (rx == holex && ry == holey) {
					Rin = 1;
					rx = -1;
					ry = -1;
					break;
				}
			}
			while (by < ry - 1 && map[by + 1][bx] == 0) {
				by++;
				if (bx == holex && by == holey) {
					Bin = 1;
					bx = -1;
					by = -1;
					break;
				}
			}
		}
	}
	else {
		while (ry < M && map[ry + 1][rx] == 0) {
			ry++;
			if (rx == holex && ry == holey) {
				Rin = 1;
				rx = -1;
				ry = -1;
				break;
			}
		}
		while (by < M && map[by + 1][bx] == 0) {
			by++;
			if (bx == holex && by == holey) {
				Bin = 1;
				bx = -1;
				by = -1;
				break;
			}
		}
	}

	node* l = newNode(bx, by, rx, ry);
	l->turn = nd.turn + 1;

	Q->end->next = l;
	Q->end = Q->end->next;
}


int attempt() {

	while (1){
		if (Q->qp->turn > 10) {
			printf("-1");
			return 0;
		}

		//only red got in
		if (Q->qp->Bx != -1 && Q->qp->Rx == -1) {
			printf("%d", Q->qp->turn);
			return 0;
		}

        //when blue got in, skip
		if (Q->qp->Bx == -1) {
			Q->qp = Q->qp->next;
			continue;
		}

		left(*Q->qp);
		right(*Q->qp);
		up(*Q->qp);
		down(*Q->qp);
		
		Q->qp = Q->qp->next;
	}


}

int main()
{
	scanf("%d", &N);
	scanf("%d", &M);

	char tok;

	int a, b, c, d;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)	{

			scanf(" %c", &tok);
			if (tok == '#') {
				map[i][j] = 1;
			}
			else if (tok == '.') {
				map[i][j] = 0;
			}
			else if (tok == 'O') {
				map[i][j] = 0;
				holex = j;
				holey = i;
			}
			else if (tok == 'B') {
				map[i][j] = 0;
				a = j;
				b = i;
			}
			else if (tok == 'R') {
				map[i][j] = 0;
				c = j;
				d = i;
			}
			else {
				return 1;
			}
		}
	}

	
	Q->start = newNode(a, b, c, d);
	Q->end = Q->start;
	Q->qp = Q->start;

	attempt();

//	left(*Q->start);
//	printf("%d,%d,%d,%d", Q->qp->next->By, Q->qp->next->Bx, Q->qp->next->Ry, Q->qp->next->Rx);

//	for (int i = 0; i < N; i++) {
//		for (int j = 0; j < M; j++) {
//			printf("%d", map[i][j]);
//		}
//		printf("\n");
//	}

    return 0;
}

djm03178 5년 전 1

랜덤 제너레이터를 만든 김에 반례 드립니다.

9 8
########
#......#
#..O.R.#
#......#
#.#B.#.#
##..#..#
##...#.#
#......#
########
correct = 1, wrong = 8

8 9
#########
##..#.O.#
#.##...##
##...#B##
##..#.#.#
##.R....#
###...###
#########
correct = -1, wrong = 4

9 6
######
##.B.#
#....#
#....#
#..R.#
#..O.#
###..#
#....#
######
correct = 6, wrong = 4

8 7
#######
#.#...#
#..#O##
#.R...#
##..B.#
#..#..#
#..#..#
#######
correct = 6, wrong = -1

9 7
#######
#.....#
###.#.#
#R...##
##....#
#.B...#
#.##.O#
#.##..#
#######
correct = 5, wrong = 4

8 10
##########
#........#
#.O......#
#..R.....#
#..#.....#
#.#......#
#....B...#
##########
correct = 7, wrong = 5

9 9
#########
#.......#
#.......#
##B.....#
#...#...#
#..R#...#
#.......#
#.O.....#
#########
correct = 3, wrong = 1

6 7
#######
#.....#
##...##
#R....#
#.##BO#
#######
correct = 3, wrong = 1

6 9
#########
###.B...#
#......##
#...R...#
#.#.O...#
#########
correct = 3, wrong = 1

8 9
#########
#.......#
#...R...#
#.....#.#
#..#....#
#...B..O#
#.......#
#########
correct = 2, wrong = 1

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

문제

문제

출처

ICPC

틀렸다고 뜨는데 제발 도와주세요ㅠㅠㅠ 주석처리했어요!

po00076 6년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말