#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; int total; //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"; // // // // // } //} void clearB() { for (int i = 0; i < 101; i++) ::fill(b[i], b[i] + 101, 0); } void clearV() { for (int i = 0; i < 101; i++) ::fill(v[i], v[i] + 101, 0); } bool isDoor(Pos cur) { int x = cur.x; int y = cur.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; } bool isKey(Pos cur) { int x = cur.x; int y = cur.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; } bool isKey(char key) { if (key >= 'a' && key <= 'z') return true; return false; } void OpenDoor(int idx) { // 내가 갈 수 없는 곳에 있는 열쇠를 이로 인해 찾게 된다면? vector d = door[idx]; for (int i = 0; i < d.size(); i++) { Pos cur = d[i]; int x = cur.x; int y = cur.y; b[y][x] = '.'; 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) { q.push({ x, y }); } else if(v[ny][nx]) q.push({ x, y }); } } } // 1. bfs 완료 전 출발 지점 찾아야 함 // 출발 지점부터 시작해서 bfs 탐색 // 조건 제한 없이 전부 돌아야 함 void beforeSt() { // 위 for (int i = 0; i < w; i++) if (b[0][i] == '$' || b[0][i] == '.' || isKey(b[0][i])) q.push({ i, 0 }); // 우 for (int i = 1; i < h - 1; i++) if (b[i][w - 1] == '$' || b[i][w - 1] == '.' || isKey(b[i][w - 1])) q.push({ w - 1,i }); // 하 for (int i = 0; i < w; i++) if (b[h - 1][i] == '$' || b[h - 1][i] == '.' || isKey(b[h - 1][i])) q.push({ i, h - 1 }); // 좌 for (int i = 1; i < h - 1; i++) if (b[i][0] == '$' || b[i][0] == '.' || isKey(b[i][0])) q.push({ 0, i }); } // 2. bfs 완료 후 출발 지점 찾아야 함 void afterSt(int& total) { // 위 for (int i = 0; i < w; i++) if (b[0][i] == '$' || b[0][i] == '.' || isKey(b[0][i])) { if (b[0][i] == '$') total++; q.push({ i, 0 }); v[0][i] = 1; } // 우 for (int i = 1; i < h - 1; i++) if (b[i][w - 1] == '$' || b[i][w - 1] == '.' || isKey(b[i][w - 1])) { if (b[i][w - 1] == '$') total++; q.push({ w - 1,i }); v[i][w - 1] = 1; } // 하 for (int i = 0; i < w; i++) if (b[h - 1][i] == '$' || b[h - 1][i] == '.' || isKey(b[h - 1][i])) { if (b[h - 1][i] == '$') total++; q.push({ i, h - 1 }); v[h - 1][i] = 1; } // 좌 for (int i = 1; i < h - 1; i++) if (b[i][0] == '$' || b[i][0] == '.' || isKey(b[i][0])) { if (b[i][0] == '$') total++; q.push({ 0, i }); v[i][0] = 1; } } void findDoor() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (isDoor({ j, i })) { door[b[i][j] - 'A'].push_back({ j,i }); } } } } void print() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) cout << b[i][j]; cout << endl; } } void solution() { int tc; cin >> tc; while (tc--) { clearB(); clearV(); for (int i = 0; i < 26; i++) door[i].clear(); total = 0; cin >> h >> w; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) cin >> b[i][j]; findDoor(); string key; cin >> key; for (int i = 0; i < key.length(); i++) { if (isKey(key[i])) { int idx = key[i] - 'a'; OpenDoor(idx); } } beforeSt(); 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 = x + dx[dir]; int ny = y + dy[dir]; if (nx < 0 || nx >= w || ny < 0 || ny >= h) continue; if (b[ny][nx] == '*' || v[ny][nx]) continue; if (isDoor({ nx, ny })) continue; if (isKey({ nx, ny })) { int idx = b[ny][nx] - 'a'; b[ny][nx] = '.'; OpenDoor(idx); door[idx].clear(); } v[ny][nx] = 1; q.push({ nx, ny }); } } clearV(); afterSt(total); 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 = 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] == '*' || isDoor({nx, ny})) continue; if (b[ny][nx] == '$') total++; q.push({ nx, ny }); v[ny][nx] = 1; } } cout << total << "\n"; //print(); } } int main() { ios::sync_with_stdio(false); cin.tie(0); solution(); return 0; }

제출 #141027

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: