#include #include #include #include #include #include using namespace std; int answer; int h, w; bool visit[101][101]; vector> buildingmap; deque> later; // 나중에 방문할 좌표 vector keys(26, 0); int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; bool checkvalid(char c, int x, int y){ if(c == '.'){ return true; }else if(c == '*'){ return false; }else if('A' <= c && c <= 'Z'){ if(keys[c - 'A'] == 1){ buildingmap[x][y] = '.'; return true; }else{ later.push_back({x, y, c}); return false; } }else if('a' <= c && c <= 'z'){ keys[c - 'a'] = 1; return true; }else if(c == '$'){ answer++; return true; } return false; } int main(){ int TC; cin >> TC; for(int tc = 0; tc < TC; tc++){ answer = 0; cin >> h >> w; later.clear(); memset(visit, false, sizeof(visit)); // visit 초기화 buildingmap.clear(); // buildingmap 초기화 buildingmap.resize(h, vector(w)); for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ cin >> buildingmap[i][j]; } } string s; cin >> s; for(int i = 0; i < 26; i++){ // key 초기화 keys[i] = 0; } if(s[0] != '0'){ for(char c : s){ keys[c - 'a'] = 1; } } // 1차 bfs // 주변 돌면서 BFS 탐색. 갈 수 있는 곳 찾음 // .일경우 계속 탐색, *일경우 탐색 x, 알파벳 대문자는 keys에서 있으면 .으로 바꾸고 탐색, 없으면 기록. 알파벳 소문자는 keys에 업데이트 // deque> dq; // 테두리 check for(int i = 0; i < w; i++){ if (checkvalid(buildingmap[0][i], 0, i) && !visit[0][i]){ visit[0][i] = true; deque> dq; dq.push_back({0, i}); while(!dq.empty()){ int px = dq.front().first; int py = dq.front().second; dq.pop_front(); for(int j = 0; j < 4; j++){ int nx = px + dx[j]; int ny = py + dy[j]; if(0 <= nx && nx < h && 0 <= ny && ny < w && !visit[nx][ny] && checkvalid(buildingmap[nx][ny], nx, ny)){ visit[nx][ny] = true; dq.push_back({nx, ny}); } } } } if (checkvalid(buildingmap[h - 1][i], h - 1, i) && !visit[h - 1][i]){ visit[h - 1][i] = true; deque> dq; dq.push_back({h - 1, i}); while(!dq.empty()){ int px = dq.front().first; int py = dq.front().second; dq.pop_front(); for(int j = 0; j < 4; j++){ int nx = px + dx[j]; int ny = py + dy[j]; if(0 <= nx && nx < h && 0 <= ny && ny < w && !visit[nx][ny] && checkvalid(buildingmap[nx][ny], nx, ny)){ visit[nx][ny] = true; dq.push_back({nx, ny}); } } } } } for(int i = 0; i < h; i++){ if (checkvalid(buildingmap[i][0], i, 0) && !visit[i][0]){ visit[i][0] = true; deque> dq; dq.push_back({i, 0}); while(!dq.empty()){ int px = dq.front().first; int py = dq.front().second; dq.pop_front(); for(int j = 0; j < 4; j++){ int nx = px + dx[j]; int ny = py + dy[j]; if(0 <= nx && nx < h && 0 <= ny && ny < w && !visit[nx][ny] && checkvalid(buildingmap[nx][ny], nx, ny)){ visit[nx][ny] = true; dq.push_back({nx, ny}); } } } } if (checkvalid(buildingmap[i][w - 1], i, w - 1) && !visit[i][w - 1]){ visit[i][w - 1] = true; deque> dq; dq.push_back({i, w - 1}); while(!dq.empty()){ int px = dq.front().first; int py = dq.front().second; dq.pop_front(); for(int j = 0; j < 4; j++){ int nx = px + dx[j]; int ny = py + dy[j]; if(0 <= nx && nx < h && 0 <= ny && ny < w && !visit[nx][ny] && checkvalid(buildingmap[nx][ny], nx, ny)){ visit[nx][ny] = true; dq.push_back({nx, ny}); } } } } } if(later.size() != 0){ bool updated = true; while (updated) { updated = false; deque> new_later; for (auto [x, y, c] : later) { if (keys[c - 'A']) { if (!visit[x][y]) { visit[x][y] = true; buildingmap[x][y] = '.'; deque> dq; dq.push_back({x, y}); while(!dq.empty()) { int px = dq.front().first; int py = dq.front().second; dq.pop_front(); for (int d = 0; d < 4; d++) { int nx = px + dx[d]; int ny = py + dy[d]; if (0 <= nx && nx < h && 0 <= ny && ny < w && !visit[nx][ny] && checkvalid(buildingmap[nx][ny], nx, ny)) { visit[nx][ny] = true; dq.push_back({nx, ny}); } } } updated = true; } } else { new_later.push_back({x, y, c}); } } later = new_later; } } cout << answer << "\n"; } }

제출 #100309

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: