[9328] 열쇠

열쇠 성공

문제

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	2337	445	267	17.440%

상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 필요하다. 상근이는 일부 열쇠를 이미 가지고 있고, 일부 열쇠는 빌딩의 바닥에 놓여져 있다.

상근이가 훔칠 수 있는 문서의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 지도의 높이와 너비 h와 w (2 ≤ h, w ≤ 100)가 주어진다. 다음 h개 줄에는 빌딩을 나타내는 w개의 문자가 주어지며, 각 문자는 다음 중 하나이다.

• '.'는 빈 공간을 나타낸다.
• '*'는 벽을 나타내며, 상근이는 벽을 통과할 수 없다.
• '$'는 상근이가 훔쳐야하는 문서이다.
• 알파벳 대문자는 문을 나타낸다.
• 알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.

마지막 줄에는 상근이가 이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.

상근이는 빌딩 밖으로 나갈 수 있다. 각각의 문에 대해서, 그 문을 열 수 잇는 열쇠의 개수는 0개, 1개, 또는 그 이상이고, 각각의 열쇠에 대해서, 그 열쇠로 열 수 있는 문의 개수도 0개, 1개, 또는 그 이상이다. 열쇠는 여러 번 사용할 수 있다.

출력

각 테스트 케이스 마다, 상근이가 훔칠 수 있는 문서의 최대 개수를 출력한다.

예제 입력 

3
5 17
*****************
.............**$*
*B*A*P*C**X*Y*.X.
*y*x*a*p**$*$**$*
*****************
cz
5 11
*.*********
*...*...*x*
*X*.*.*.*.*
*$*...*...*
***********
0
7 7
*ABCDE*
X.....F
W.$$$.G
V.$$$.H
U.$$$.J
T.....K
*SQPML*
irony

예제 출력 

3
1
0

힌트

문제를 읽었을 때, 굉장히 쉬운 문제라고 생각해서 낮은 정답률에 의아했습니다.

하지만 풀다보니까 열쇠가 없어서 방문하지 못한 곳의 열쇠를 나중에 얻었을 경우를

처리해주는 부분이 까다로웠습니다.

dfs를 써서 탐색을 한다면 동서남북 방향으로 이동할 때 키가 있으면 방문하면 되는 것이고,

없을 경우에는 벡터에 문의 좌표를 넣었습니다.

그리고 dfs탐색이 끝나면

벡터에 들어있는 문을 탐색하여 키를 얻는다면 한번 더 벡터의 처음부터 탐색을 하고,

만약 키를 얻을 수 없다면 while문을 종료하고 얻은 서류 값을 출력하면 됩니다.

추가로!!! 시작점이 없기 때문에 굉장히 고민했는데 방법은 간단합니다.

(0, 0)
	(1, 1)
				(4, 4)
					(5, 5)

h = 4, w = 4일 경우에 우리가 입력 받는 부분은 빨간색입니다.

(0, 0)부터 dfs로 탐색을 한다면 빨간색의 테두리에 문이라면 키가 있을 때 들어갈 수 있고,

없다면 벡터에 넣습니다.

'.'이라면 맵안으로 들어갈 것입니다.

#include <cstdio>
#include <iostream>
#include <vector>
#include <string.h>
 
#define ll long long
#define MAX_SIZE 110
#define ALPHA_SIZE 26
using namespace std;
 
vector<pair<int, int> > v;
 
int h, w;
char map[MAX_SIZE][MAX_SIZE];
bool visit[MAX_SIZE][MAX_SIZE];
bool key[ALPHA_SIZE];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0,0};
bool flag;
 
void input()
{
    scanf("%d %d", &h, &w);
    getchar();
 
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            map[i][j] = getchar();
        }
        getchar();
    }
 
    while(1)
    {
        char c = getchar();
        if(c == '0' || c == '\n')break;
        else key[c - 'a'] = 1;
    }
}
 
int dfs(int x, int y)//0,0
{
    int ret = 0;
 
    visit[x][y] = 1;
 
    if(map[x][y] == '$') ret++;
 
    else if(map[x][y] >= 'a' && map[x][y] <= 'z')
    {
        key[map[x][y] - 'a'] = 1;
        flag = 1;
    }
 
 
    for(int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
 
        if(nx < 0 || ny < 0 || nx > h + 1|| ny > w + 1) continue;
        if(map[nx][ny] == '*') continue;
        if(visit[nx][ny]) continue;
 
        if(map[nx][ny] >= 'A' && map[nx][ny] <= 'Z' && !key[map[nx][ny] - 'A'])
        {
            v.push_back(make_pair(nx, ny));
            continue;
        }
 
        ret += dfs(nx, ny);
    }
 
 
    return ret;
}
 
 
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        //초기화 부분
        memset(visit, 0, sizeof(visit));
        memset(key, 0, sizeof(key));
        memset(map, 0, sizeof(map));
        v.clear();
 
        input(); // 입력 부분
 
        int ret = dfs(0, 0); // dfs 첫 탐색
 
        while(1) // 와일문을 반복하며 백터를 탐색
        {
            flag = 0;
 
            for(int i = 0; i < v.size(); i++)
            {
                if(key[map[v[i].first][v[i].second] - 'A'])
                    ret += dfs(v[i].first, v[i].second);
            }
 
            if(flag == 0) break; // 키를 얻은 것이 없다면 탈출
        }
 
        printf("%d\n", ret);
    }
    return 0;
}