#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; int dx[] = { 1, 0, -1, 0 }; int dy[] = { 0, 1, 0, -1 }; char b[101][101]; int v[101][101]; int h, w; int tc; struct Pos { Pos(int x, int y) : x(x), y(y) { } int x, y; }; vector door[26]; vector st; queue q; bool isDoor(Pos pos) { int x = pos.x; int y = pos.y; char ch = b[y][x]; if (x < 0 || x >= w || y < 0 || y >= h) return false; if (b[y][x] >= 'A' && b[y][x] <= 'Z') return true; return false; } bool isKey(Pos pos) { int x = pos.x; int y = pos.y; if (x < 0 || x >= w || y < 0 || y >= h) return false; if (b[y][x] >= 'a' && b[y][x] <= 'z') return true; return false; } void FindSt() { // 위 for (int i = 0; i < w; i++) if (b[0][i] == '.' || b[0][i] == '$') st.push_back({ i, 0 }); // 우 for (int i = 0; i < h; i++) if (b[i][w - 1] == '.' || b[i][w - 1] == '$') st.push_back({ w - 1, i }); // 하 for (int i = 0; i < w; i++) if (b[h - 1][i] == '.' || b[h - 1][i] == '$') st.push_back({ i, h - 1 }); // 좌 for (int i = 0; i < h; i++) if (b[i][0] == '.' || b[i][0] == '$') st.push_back({ 0, i }); } void findKey(int idx) { vector open = door[idx]; for (int i = 0; i < open.size(); i++) { int x = open[i].x; int y = open[i].y; for (int dir = 0; dir < 4; dir++) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue; if (v[ny][nx]) continue; b[y][x] = '.'; q.push({ nx, ny }); } } } void print() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) cout << b[i][j]; cout << endl; } } void Solution() { cin >> tc; while (tc--) { for (int i = 0; i < 101; i++) { ::fill(b[i], b[i] + 101, 0); ::fill(v[i], v[i] + 101, 0); } // 1. 입력 받은 문들 저장 // 2. 미리 소지한 열쇠로 문 열기 // 3. 입구 찾기 // 4. BFS탐색 // 5. 열쇠를 찾았는데 해당 문 주변에 탐색 흔적이 없으면 // continue, 있다면 q에 푸시 st.clear(); cin >> h >> w; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> b[i][j]; if (isDoor({j, i})) { int idx = b[i][j] - 'A'; door[idx].push_back({ j, i }); } } } string str; cin >> str; for (int i = 0; i < str.length(); i++) { if (str[i] >= 'a' && str[i] <= 'z') { int idx = str[i] - 'a'; for (int size = 0; size < door[idx].size(); size++) { int x = door[idx][size].x; int y = door[idx][size].y; b[y][x] = '.'; } door[idx].clear(); } } FindSt(); for (int i = 0; i < st.size(); i++) q.push(st[i]); int total = 0; while (!q.empty()) { Pos cur = q.front(); q.pop(); int x = cur.x; int y = cur.y; for (int dir = 0; dir < 4; dir++) { int nx = dx[dir] + x; int ny = dy[dir] + y; if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue; if (v[ny][nx] || b[ny][nx] == '*') continue; if (isDoor({nx, ny})) continue; else if (isKey({nx, ny})) { int idx = b[ny][nx] - 'a'; findKey(idx); v[ny][nx] = 1; continue; } v[ny][nx] = 1; q.push({ nx, ny }); } } for (int i = 0; i < 101; i++) { ::fill(v[i], v[i] + 101, 0); } st.clear(); FindSt(); for (int i = 0; i < st.size(); i++) q.push(st[i]); while (!q.empty()) { Pos cur = q.front(); q.pop(); int x = cur.x; int y = cur.y; if (v[y][x] == 0) { if (b[y][x] == '$') total++; v[y][x] = 1; } for (int dir = 0; dir < 4; dir++) { int nx = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue; if (v[ny][nx]) continue; if (b[ny][nx] != '.' && b[ny][nx] != '$') continue; if (b[ny][nx] == '$') total++; v[ny][nx] = 1; q.push({ nx, ny }); } } cout << total << "\n"; } } int main() { ios::sync_with_stdio(false); cin.tie(0); Solution(); return 0; }

제출 #140828

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: