글 읽기 - 예외 케이스를 못찾겠네요;

na982 7년 전 0

코드를 계속 간결하게수정 했는데;

어디가 잘못되어있는건지 잘 모르겠네요;

$를 만나면 결과값을 증가.

열쇠를 만나면, 해당하는 문을 모두 제거하고, 이전에 방문했던 문이면, 순간이동.

탐색중에 문을 만나면 방문플래그만 체크하고 더이상 탐색은 하지 않음.

위의 로직으로 구현하였습니다.

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

typedef struct POSITION {
	int y, x;
	char mark;
	POSITION() {}
	POSITION(int _y, int _x, char _mark) {
		y = _y, x = _x, mark = _mark;
	}
};

//상 하 좌 우
const int dy[4] = { -1, 1, 0, 0 };
const int dx[4] = { 0, 0, -1, 1 };

int h, w;
char map[102][102];
int visited[102][102];
vector<POSITION> door;

void map_update(queue<POSITION>& q, char key) {
	for (int k = 0; k < door.size(); ++k) {
		if ((door[k].mark - 'A') == (key - 'a')) {
			map[door[k].y][door[k].x] = '.';
			if (visited[door[k].y][door[k].x] == 1) {
				q.push(POSITION(door[k].y, door[k].x, '.'));
			}
		}
	}
}

void next_move(queue<POSITION>& q, int y, int x) {
	if (visited[y][x] == 0 && map[y][x] != '*') {
		visited[y][x] = 1;
		if (!('A' <= map[y][x] && map[y][x] <= 'Z')) {
			q.push(POSITION(y, x, map[y][x]));
		}
	}
}

int main()
{
	int tc;
	scanf("%d", &tc);
	while (tc--) {
		scanf("%d %d", &h, &w);
		queue<POSITION> q;
		door.clear();
		memset(map, 0, sizeof(map));
		memset(visited, 0, sizeof(visited));
		for (int y = 1; y <= h; ++y) {
			scanf("%s", &map[y][1]);
			for (int x = 1; x <= w; ++x) {
				if ('A' <= map[y][x] && map[y][x] <= 'Z') {
					door.push_back(POSITION(y, x, map[y][x]));
				}
				if ('.' == map[y][x] && ((y == 1) || (y == h) || (x == 1) || (x == w))) {
					q.push(POSITION(y, x, map[y][x]));
					visited[y][x] = 1;
				}
			}
		}

		for (int y = 0; y <= h + 1; ++y)	map[y][0] = '*', map[y][w + 1] = '*';
		for (int x = 0; x <= w + 1; ++x)	map[0][x] = '*', map[h + 1][x] = '*';

		char key[52] = { 0, };
		scanf("%s", key);
		for (int i = 0; key[i] != 0; ++i) {
			map_update(q, key[i]);
		}

		int ret = 0;
		while (!q.empty()) {
			POSITION here = q.front();	q.pop();
			if (here.mark == '$')	ret++;
			if ('a' <= here.mark && here.mark <= 'z') {
				map_update(q, here.mark);
			}

			for (int dir = 0; dir < 4; ++dir) {
				next_move(q, here.y + dy[dir], here.x + dx[dir]);
			}
		}
		printf("%d\n", ret);
	}

	return 0;
}

sosfd 7년 전 3

2 2

5 11
*x*********
*...*...*.*
*X*.*.*.*.*
*$*...*...*
***********
0

위와 같은 테스트 케이스에서 답이 제대로 안나오네요.

na982 7년 전 0

감사합니다~

조금있따가 다시 한번 풀어봐야겠네요~ㅋㅋㅋ

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

문제

문제

출처

ICPC

예외 케이스를 못찾겠네요;

na982 7년 전 0

sosfd 7년 전 3

na982 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말