문제:
9328번: 열쇠
문제 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다. 상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다. 각
www.acmicpc.net
코드:
아이템 주워먹고 맵에서 지우기!
/* 1. 아이템 먹고 맵에서 지우기 */
#include <iostream>
#include <string>
#include <vector>
#define is_lc(ch) ('a' <= (ch) && (ch) <= 'z')
#define is_uc(ch) ('A' <= (ch) && (ch) <= 'Z')
#define uc(ch) (ch - 'a' + 'A')
#define IN(r, c) (0 <= (r) && (r) < R && 0 <= (c) && (c) < C)
using namespace std;
typedef pair<int, int> p;
int T, tc, R, C;
char map[104][104];
//vector<p> door['Z' + 1]; // 초기화 완료
int key['Z' + 1]; // tc
//vector<p> str; // 초기화 완료
int ans;
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
// dfs1
int vst[104][104], v; // tc
bool dfs(int r, int c) {
vst[r][c] = v;
bool ret = 0;
if (map[r][c] == '$') {
++ans;
map[r][c] = '.';
}
else if (is_lc(map[r][c])) {
key[uc(map[r][c])] = tc;
map[r][c] = '.';
ret = 1;
}
for (int d = 0; d < 4; ++d) {
int nr = r + dr[d], nc = c + dc[d];
if (map[nr][nc] == '*') continue;
if (is_uc(map[nr][nc]) && key[map[nr][nc]] != tc) continue;
if (vst[nr][nc] == v) continue;
ret |= dfs(nr, nc);
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> T;
for (tc = 1; tc <= T; ++tc) {
cin >> R >> C;
for (auto r : { 0, R + 3 })
fill(map[r], map[r] + C + 4, '*');
for (auto r : { 1, R + 2 }) {
map[r][0] = map[r][C + 3] = '*';
fill(map[r] + 1, map[r] + C + 3, '.');
}
for (int r = 2; r < R + 2; ++r) {
map[r][0] = map[r][C + 3] = '*';
map[r][1] = map[r][C + 2] = '.';
for (int c = 2; c < C + 2; ++c)
cin >> map[r][c];
}
string keys; cin >> keys;
for (auto ch : keys)
key[uc(ch)] = tc;
ans = 0;
for (++v; dfs(1, 1); ++v);
cout << ans << '\n';
}
return 0;
}