글 읽기 - 95퍼에서 틀립니다. 정답 소스와 비교해도 다른점을 모르겠습니다.

baj2121 3년 전 0

BFS로 풀었고 게시판에 현재 올라온 테케 전부 맞았는데 95퍼에서 자꾸 틀렸다고 나오네요,,, 도대체 어디가 틀렸는지 전혀 모르겠습니다.

구현은 1시간 정도 걸려서 했는데, 오류 찾는다고 3시간 넘게 썼네요...

반례나 어디가 틀렸는지 알려주세요 부탁드립니다...

#include<iostream>
#include <string>
#include <vector>
#include<queue>
#include<algorithm>

using namespace std;



int N, M;

int posy, posx;
bool visit[10][10];
char arr[10][10];

struct Node {
	int y;
	int x;
	int cost;
};

int main(void)
{
	cin >> N >> M;

	queue<Node> red;
	queue<Node> blue;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 'R')
			{
				red.push({ i,j,1 });
				arr[i][j] = '.';
			}
			else if (arr[i][j] == 'B')
			{
				blue.push({ i,j,1 });
				arr[i][j] = '.';
			}
			else if (arr[i][j] == 'O')
			{
				posy = i;
				posx = j;
				arr[i][j] = '.';
			}

		}
	}


	while (!red.empty())
	{
		int redy = red.front().y;
		int redx = red.front().x;
		int redcost = red.front().cost;

		int bluey = blue.front().y;
		int bluex = blue.front().x;
		int bluecost = blue.front().cost;


		red.pop();
		blue.pop();

		if (redcost > 10 )
		{
			cout << -1 << endl;
			return 0;
		}

		if (arr[redy - 1][redx] != '#' || arr[bluey - 1][bluex] != '#')
		{
			if (redy <= bluey)
			{
				bool flag = false;
				int tredy = redy;
				while (arr[tredy - 1][redx] != '#')
				{
					tredy--;
					if (tredy == posy && redx == posx)
					{
						flag = true;
						break;
					}
				}

				if (!flag)
				{
					visit[tredy][redx] = true;
				}

				bool flag2 = false;
				int tbluey = bluey;
				while (!visit[tbluey - 1][bluex] && arr[tbluey - 1][bluex] != '#')
				{
					tbluey--;
					if (tbluey == posy && bluex == posx)
					{
						flag2 = true;
						break;
					}
				}

				if (flag && !flag2)
				{
					cout << redcost << endl;
					return 0;
				}
				else if (!flag && !flag2)
				{
					red.push({ tredy,redx,redcost + 1 });
					blue.push({ tbluey,bluex,bluecost + 1 });
					
				}
				visit[tredy][redx] = false;
			}
			else
			{
				bool flag2 = false;
				int tbluey = bluey;
				while (arr[tbluey - 1][bluex] != '#')
				{
					tbluey--;
					if (tbluey == posy && bluex == posx)
					{
						flag2 = true;
						break;
					}
				}

				if (!flag2)
				{
					visit[tbluey][bluex] = true;
				}

				bool flag = false;
				int tredy = redy;
				while (!visit[tredy - 1][redx] && arr[tredy - 1][redx] != '#')
				{
					tredy--;
					if (tredy == posy && redx == posx)
					{
						flag = true;
						break;
					}
				}

				if (flag && !flag2)
				{
					cout << redcost << endl;
					return 0;
				}
				else if (!flag && !flag2)
				{
					red.push({ tredy,redx,redcost + 1 });
					blue.push({ tbluey,bluex,bluecost + 1 });
                    visit[tbluey][bluex] = false;
					
				}
				

			}
		}

		if (arr[redy + 1][redx] != '#' || arr[bluey + 1][bluex] != '#')
		{
			if (redy > bluey)
			{
				bool flag = false;
				int tredy = redy;
				while (arr[tredy + 1][redx] != '#')
				{
					tredy++;
					if (tredy == posy && redx == posx)
					{
						flag = true;
						break;
					}
				}

				if (!flag)
				{
					visit[tredy][redx] = true;
				}

				bool flag2 = false;
				int tbluey = bluey;
				while (!visit[tbluey + 1][bluex] && arr[tbluey + 1][bluex] != '#')
				{
					tbluey++;
					if (tbluey == posy && bluex == posx)
					{
						flag2 = true;
						break;
					}
				}

				if (flag && !flag2)
				{
					cout << redcost << endl;
					return 0;
				}
				else if (!flag && !flag2)
				{
					red.push({ tredy,redx,redcost + 1 });
					blue.push({ tbluey,bluex,bluecost + 1 });
					
				}
				visit[tredy][redx] = false;

			}
			else
			{
				bool flag2 = false;
				int tbluey = bluey;
				while (arr[tbluey + 1][bluex] != '#')
				{
					tbluey++;
					if (tbluey == posy && bluex == posx)
					{
						flag2 = true;
						break;
					}
				}

				if (!flag2)
				{
					visit[tbluey][bluex] = true;
				}

				bool flag = false;
				int tredy = redy;
				while (!visit[tredy + 1][redx] && arr[tredy + 1][redx] != '#')
				{
					tredy++;
					if (tredy == posy && redx == posx)
					{
						flag = true;
						break;
					}
				}

				if (flag && !flag2)
				{
					cout << redcost << endl;
					return 0;
				}
				else if (!flag && !flag2)
				{
					red.push({ tredy,redx,redcost + 1 });
					blue.push({ tbluey,bluex,bluecost + 1 });
                    visit[tbluey][bluex] = false;
					
				}
				

			}
		}


		if (arr[redy][redx - 1] != '#' || arr[bluey][bluex - 1] != '#')
		{
			if (redx <= bluex)
			{
				bool flag = false;
				int tredx = redx;
				while (arr[redy][tredx - 1] != '#')
				{
					tredx--;
					if (redy == posy && tredx == posx)
					{
						flag = true;
						break;
					}
				}

				if (!flag)
				{
					visit[redy][tredx] = true;
				}

				bool flag2 = false;
				int tbluex = bluex;
				while (!visit[bluey][tbluex - 1] && arr[bluey][tbluex - 1] != '#')
				{
					tbluex--;
					if (bluey == posy && tbluex == posx)
					{
						flag2 = true;
						break;
					}
				}

				if (flag && !flag2)
				{
					cout << redcost << endl;
					return 0;
				}
				else if (!flag && !flag2)
				{
					red.push({ redy,tredx,redcost + 1 });
					blue.push({ bluey,tbluex,bluecost + 1 });
					
				}
				visit[redy][tredx] = false;

			}
			else
			{
				bool flag2 = false;
				int tbluex = bluex;
				while (arr[bluey][tbluex - 1] != '#')
				{
					tbluex--;
					if (bluey == posy && tbluex == posx)
					{
						flag2 = true;
						break;
					}
				}

				if (!flag2)
				{
					visit[bluey][tbluex] = true;
				}

				bool flag = false;
				int tredx = redx;
				while (!visit[redy][tredx - 1] && arr[redy][tredx - 1] != '#')
				{
					tredx--;
					if (redy == posy && tredx == posx)
					{
						flag = true;
						break;
					}
				}

				if (flag && !flag2)
				{
					cout << redcost << endl;
					return 0;
				}
				else if (!flag && !flag2)
				{
					red.push({ redy,tredx,redcost + 1 });
					blue.push({ bluey,tbluex,bluecost + 1 });
                    visit[bluey][tbluex] = false;
					
				}
				

			}

		}


		if (arr[redy][redx + 1] != '#' || arr[bluey][bluey + 1] != '#')
		{
			if (redx > bluex)
			{
				bool flag = false;
				int tredx = redx;
				while (arr[redy][tredx + 1] != '#')
				{
					tredx++;
					if (redy == posy && tredx == posx)
					{
						flag = true;
						break;
					}
				}

				if (!flag)
				{
					visit[redy][tredx] = true;
				}

				bool flag2 = false;
				int tbluex = bluex;
				while (!visit[bluey][tbluex + 1] && arr[bluey][tbluex + 1] != '#')
				{
					tbluex++;
					if (bluey == posy && tbluex == posx)
					{
						flag2 = true;
						break;
					}
				}

				if (flag && !flag2)
				{
					cout << redcost << endl;
					return 0;
				}
				else if (!flag && !flag2)
				{
					red.push({ redy,tredx,redcost + 1 });
					blue.push({ bluey,tbluex,bluecost + 1 });
					
				}
				visit[redy][tredx] = false;
			}
			else
			{
				bool flag2 = false;
				int tbluex = bluex;
				while (arr[bluey][tbluex + 1] != '#')
				{
					tbluex++;
					if (bluey == posy && tbluex == posx)
					{
						flag2 = true;
						break;
					}
				}

				if (!flag2)
				{
					visit[bluey][tbluex] = true;
				}

				bool flag = false;
				int tredx = redx;
				while (!visit[redy][tredx + 1] && arr[redy][tredx + 1] != '#')
				{
					tredx++;
					if (redy == posy && tredx == posx)
					{
						flag = true;
						break;
					}
				}

				if (flag && !flag2)
				{
					cout << redcost << endl;
					return 0;
				}
				else if (!flag && !flag2)
				{
					red.push({ redy,tredx,redcost + 1 });
					blue.push({ bluey,tbluex,bluecost + 1 });
                    visit[bluey][tbluex] = false;
					
				}
				

			}
		}

	}

	cout << -1 << endl;
	
}

tony9402 3년 전 5

반례 드립니다.

10 6
######
#O##.#
#.#.##
#..#.#
#B...#
###R##
#..#.#
###..#
#....#
######

answer : 4
output : -1

tony9402 3년 전 7

추가 반례 드립니다.

7 10
##########
#..###..##
#....#####
###O..####
##B..##..#
##.#R#..##
##########

answer : 3

7 6
######
#.####
##R#.#
##..##
#B...#
#O####
######

answer : 4

9 6
######
##.#.#
#.#.##
#..#.#
#B..##
#R#.##
#.##.#
#O.###
######

answer : 2

6 9
#########
#..#...R#
#..##.#.#
#.###OB.#
####.#..#
#########

answer : 3

8 6
######
#..#.#
######
#.##.#
#.OB.#
##.#R#
###..#
######

answer : 3

8 5
#####
#O.##
#B.##
#..##
#..##
##.R#
#...#
#####

answer : 5

7 9
#########
#..####.#
##.##R.##
##.###..#
###.##B##
#O......#
#########

answer : 5

7 7
#######
#.###R#
##....#
#..#.##
##.#OB#
##....#
#######

answer : 7

6 5
#####
###R#
##..#
#OB.#
#.#.#
#####

answer : 3

emrdbs123 2년 전 0

위의 반례 중

7 9
#########
#..####.#
##.##R.##
##.###..#
###.##B##
#O......#
#########

는

down right down left로 answer 가 4 인거 같아요!

tony9402 2년 전 1

@emrdbs123

문제 일부에 "빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다." 해당 문장이 있습니다.

위에서 설명해주신 방법대로 진행하면 빨간 구슬과 파란 구슬이 동시에 빠져서 실패가 됩니다.

right, up, right, down, left 이 총 5가지 단계로 답이 5가 됩니다 !

emrdbs123 2년 전 0

와 엄청 빠른 피드백 감사합니다.

빨리 고통에서 해방되고 싶네요 ㅎㅎ

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

문제

문제

출처

ICPC

95퍼에서 틀립니다. 정답 소스와 비교해도 다른점을 모르겠습니다.

baj2121 3년 전 0

tony9402 3년 전 5

tony9402 3년 전 7

emrdbs123 2년 전 0

tony9402 2년 전 1

emrdbs123 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말