글 읽기 - 틀린 TC를 못찾아 몇시간째 헤매고 있습니다ㅠ.ㅠ

ll1000wooll 6년 전 0

BFS로 방향 그대로 보내는 경우, 거울설치가 될때에는 반사되는 방향으로 보내는 경우 두가지 추가해서

4방향 + 위치 체크 배열로 각각 거울 갯수를 카운트 해주었는데요...

틀린 테스트케이스가 도저히 보이질 않습니다...ㅠ.ㅠ

고수님들의 도움부탁드립니다...

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
#define INF 987654321
using namespace std;
int n;
string s[52];
struct st{
	int x, y, cnt, arrow;
};
st str;
queue <st> q;
bool check[52][52][4];
int stx, sty;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
int ans = INF;

void init() {
	while (!q.empty()) q.pop();
	for (int i = 0; i < 52; i++) {
		for (int k = 0; k < 52; k++) {
			for (int g = 0; g < 4; g++) {
				check[i][k][g] = false;
			}
		}
	}
}

void bfs(int flag) {
	init();
	q.push({ stx, sty, 0, flag });
	check[stx][sty][flag] = true;
	while (!q.empty()) {
		str = q.front();
		q.pop();
		int qx = str.x;
		int qy = str.y;
		int qc = str.cnt;
		int qa = str.arrow;
		if (s[qx][qy] == '#') {
			if (ans > qc) {
				ans = qc;
			}
			continue;
		}
		int fx = qx + dx[qa];
		int fy = qy + dy[qa];
		if (fx >= 0 && fx < n && fy >= 0 && fy < n) {
			if (check[fx][fy][qa] == false && s[fx][fy] != '*'){
				check[fx][fy][qa] = true;
				q.push({ fx,fy,qc,qa });
			}
		}

		if (s[qx][qy] != '!') continue;
		if (qa == 1) { //밑을 향해 들어왔으면
			//첫번째 거울
			fx = qx + dx[2];
			fy = qy + dy[2];
			if (fx >= 0 && fx < n && fy >= 0 && fy < n) {
				if (check[fx][fy][2] == false && s[fx][fy] != '*'){
					check[fx][fy][2] = true;
					q.push({ fx,fy,qc + 1, 2 });
				}
			}
			//두번째 거울
			fx = qx + dx[0];
			fy = qy + dy[0];
			if (fx >= 0 && fx < n && fy >= 0 && fy < n) {
				if (check[fx][fy][0] == false && s[fx][fy] != '*'){
					check[fx][fy][0] = true;
					q.push({ fx,fy,qc + 1, 0 });
				}
			}
		}
		else if (qa == 3) {
			fx = qx + dx[0];
			fy = qy + dy[0];
			if (fx >= 0 && fx < n && fy >= 0 && fy < n) {
				if (check[fx][fy][0] == false && s[fx][fy] != '*') {
					check[fx][fy][0] = true;
					q.push({ fx,fy,qc + 1, 0 });
				}
			}
			//두번째 거울
			fx = qx + dx[2];
			fy = qy + dy[2];
			if (fx >= 0 && fx < n && fy >= 0 && fy < n) {
				if (check[fx][fy][2] == false && s[fx][fy] != '*') {
					check[fx][fy][2] = true;
					q.push({ fx,fy,qc + 1, 2 });
				}
			}
		}
		else if (qa == 0) {
			fx = qx + dx[3];
			fy = qy + dy[3];
			if (fx >= 0 && fx < n && fy >= 0 && fy < n) {
				if (check[fx][fy][3] == false && s[fx][fy] != '*') {
					check[fx][fy][3] = true;
					q.push({ fx,fy,qc + 1, 3 });
				}
			}
			//두번째 거울
			fx = qx + dx[1];
			fy = qy + dy[1];
			if (fx >= 0 && fx < n && fy >= 0 && fy < n) {
				if (check[fx][fy][1] == false && s[fx][fy] != '*') {
					check[fx][fy][1] = true;
					q.push({ fx,fy,qc + 1, 1 });
				}
			}
		}
		else {
			fx = qx + dx[1];
			fy = qy + dy[1];
			if (fx >= 0 && fx < n && fy >= 0 && fy < n) {
				if (check[fx][fy][1] == false && s[fx][fy] != '*') {
					check[fx][fy][1] = true;
					q.push({ fx,fy,qc + 1, 1 });
				}
			}
			//두번째 거울
			fx = qx + dx[3];
			fy = qy + dy[3];
			if (fx >= 0 && fx < n && fy >= 0 && fy < n) {
				if (check[fx][fy][3] == false && s[fx][fy] != '*'){
					check[fx][fy][3] = true;
					q.push({ fx,fy,qc + 1, 3 });
				}
			}
		}
	}
	return;
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	bool st_check = false;
	for (int i = 0; i < n; i++) {
		for (int k = 0; k < n; k++) {
			if (s[i][k] == '#') {
				stx = i;
				sty = k;
				s[i][k] = '*';
				st_check = true;
				break;
			}
		}
		if (st_check) break;
	}
	for (int i = 0; i < 4; i++) {
		bfs(i);
	}
	cout << ans << "\n";
	return 0;
}

kdk8361 6년 전 3

8
***#****
*!.!..!*
*......*
*..*...*
*!!....*
*.!!..!*
*......*
***#****

4 가 나와야 합니다.

ll1000wooll 6년 전 0

감사합니다 덕분에 해결했습니다!^^

더 짧은 경로로 탐색이 필요한 경우 큐에 값이 들어가질 않았습니다.

방문 check를 카운트 값으로 비교해줘야하는 것이 필요했네요ㅎㅎ

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

문제

문제

출처

ICPC

틀린 TC를 못찾아 몇시간째 헤매고 있습니다ㅠ.ㅠ

ll1000wooll 6년 전 0

kdk8361 6년 전 3

ll1000wooll 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말