글 읽기 - 문제푸는 방식에 대한 질문입니다.

aza1200 4년 전 0

코드는 다 안읽어보셔도 될거같습니다.

저 같은경우는 계속들리다가 (34퍼센트에서 계속 틀렸떤거 같네요)

질문계시판을 읽어보았는데 사람들이 다 10번이상 이동했을시에 -1을 출력하더라고요

그래서 저 또한 10번이상 이동시 -1을 출력하도록 했는데 (68번째줄)

바로 맞더라고요!!!

일반적인 큐에다가 visit 배열 체크하면서 bfs 를 할시 그리고 10번째이상이라는 조건을 안할시 틀리던데 이 이유는 무엇인가요?

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

int N, M;
char arr[20][20];
bool visit[20][20][20][20];
int first_redr, first_redc, first_bluer, first_bluec;
int holer, holec;

int rowd[4] = { 0,0,1,-1 };
int cold[4] = { 1,-1,0,0 };
//오 왼 아래 위

struct status {
	int redr;
	int redc;
	int bluer;
	int bluec;
	status(int a,int b,int c,int d): redr(a),redc(b),bluer(c),bluec(d){}
};

bool check(int i, status now) {
	bool whois = false; // 거짓이면 빨간색먼저 true 면파란색먼저
	if (i == 0) {
		//오른쪽
		if (now.bluec > now.redc) whois = true;
	}
	else if (i == 1) {
		//왼쪽
		if (now.bluec < now.redc) whois = true;
	}
	else if (i == 2) {
		//아래쪽
		if (now.bluer > now.redr) whois = true;
	}
	else {
		//위쪽
		if (now.bluer < now.redr) whois = true;
	}
	return whois;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i <= 13; i++) for (int j = 0; j <= 13; j++) arr[i][j] = '#';

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'B')first_bluer = i, first_bluec = j;
			else if (arr[i][j] == 'R') first_redr = i, first_redc = j;
			else if (arr[i][j] == 'O')holer = i, holec = j;
		}
	}

	queue<status> q;
	q.push(status(first_redr, first_redc, first_bluer, first_bluec));
	visit[first_redr][first_redc][first_bluer][first_bluec] = true;
	long long cnt = 0;

	while (!q.empty()) {
		int qsize = q.size();
		cnt++;
		if (cnt == 11) break;
		while (qsize--) {
			status now = q.front(); q.pop();
			for (int i = 0; i < 4; i++) {
				bool who = check(i, now);
				int next_redr = now.redr, next_redc =  now.redc;
				int next_bluer= now.bluer, next_bluec = now.bluec;
				if (who) {
					while (arr[next_bluer + rowd[i]][next_bluec + cold[i]]!='#' && arr[next_bluer + rowd[i]][next_bluec + cold[i]] != 'O') {
						next_bluer += rowd[i];
						next_bluec += cold[i];
						//파랑공 정하기
					}
					if (arr[next_bluer + rowd[i]][next_bluec + cold[i]] == 'O') next_bluer += rowd[i], next_bluec += cold[i];
					
					while (arr[next_redr + rowd[i]][next_redc + cold[i]] != '#' && arr[next_redr + rowd[i]][next_redc + cold[i]] != 'O') {
						if (next_redr + rowd[i] == next_bluer && next_redc + cold[i] == next_bluec) break;
						next_redr += rowd[i];
						next_redc += cold[i];
						//빨간공정하기
					}
					if (arr[next_redr + rowd[i]][next_redc + cold[i]] == 'O') next_redr += rowd[i], next_redc += cold[i];
					
				}
				else {
					while (arr[next_redr + rowd[i]][next_redc + cold[i]] != '#' && arr[next_redr + rowd[i]][next_redc + cold[i]] != 'O') {
						next_redr += rowd[i];
						next_redc += cold[i];
						//빨간공정하기
					}
					if (arr[next_redr + rowd[i]][next_redc + cold[i]] == 'O') next_redr += rowd[i], next_redc += cold[i];

					while (arr[next_bluer + rowd[i]][next_bluec + cold[i]] != '#' && arr[next_bluer + rowd[i]][next_bluec + cold[i]] != 'O') {
						if (next_bluer+rowd[i] == next_redr && next_bluec+cold[i] == next_redc) break;
						next_bluer += rowd[i];
						next_bluec += cold[i];
						//파랑공 정하기
					}
					if (arr[next_bluer + rowd[i]][next_bluec + cold[i]] == 'O') next_bluer += rowd[i], next_bluec += cold[i];


				}
				//다음에 들어갈 공의 위치다 정해놨어야한다. 
				if (next_bluer == holer && next_bluec == holec) {
					visit[next_redr][next_redc][next_bluer][next_bluec] = true;
					continue;
				}
				else if (next_bluer == next_redr && next_bluec == next_redc) {
					visit[next_redr][next_redc][next_bluer][next_bluec] = true;
					continue;
				}
				else if (next_redr == holer && next_redc == holec) {
					cout << cnt << "\n";
					return 0;
				}
				else if (!visit[next_redr][next_redc][next_bluer][next_bluec]) {
					q.push(status(next_redr,next_redc,next_bluer,next_bluec));
					visit[next_redr][next_redc][next_bluer][next_bluec] = true;
				}

			}



		}

	}


	cout << -1 << "\n";
}










/*
if (now.redr == holer && now.redc == holec) {
cout << cnt << "\n";
return 0;
}
else if (now.bluer == holer && now.bluec == holec) continue;
*/

rhdqor213 4년 전 1

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

aza1200 4년 전 0

헠 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 하.... 이런거 하나 못읽고 문제풀었다니..... ㅠ 감사합니다 갈길이 멀군요 ㅠ

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

문제

문제

출처

ICPC

문제푸는 방식에 대한 질문입니다.

aza1200 4년 전 0

rhdqor213 4년 전 1

aza1200 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말