열쇠 - 9328

//9328 - 열쇠
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int ans;
int N, M;
int arr[100][100];
vector<vector<int>> adj;
vector<vector<bool>> visit;
bool key[26];
queue<int> door[26];
int xarr[4] = {0, 0, -1, 1};
int yarr[4] = {1, -1, 0, 0};
queue<int> canGo;
 
int convert(int x, int y)
{
    return x * M + y;
}
 
pair<int, int> back(int x)
{
    pair<int, int> ret;
    ret.first = x / M;
    ret.second = x % M;
    return ret;
}
 
char toSmall(char c)
{
    char gap = c - 'A';
    return 'a' + gap;
}
 
void init()
{
    for (int i = 0; i < 26; ++i)
    {
        key[i] = false;
        door[i] = queue<int>();
    }
    ans = 0;
    canGo = queue<int>();
    cin >> N >> M;
    string s;
    for (int i = 0; i < N; ++i)
    {
        cin >> s;
        for (int j = 0; j < M; ++j)
            arr[i][j] = s[j];
    }
    adj = vector<vector<int>>(N * M);
    visit = vector<vector<bool>>(N, vector<bool>(M, false));
    cin >> s;
    if (s[0] != '0')
        for (int i = 0; i < s.size(); ++i)
            key[s[i] - 'a'] = true;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            if (arr[i][j] != '*')
            {
                for (int k = 0; k < 4; ++k)
                    if (i + xarr[k] >= 0 && i + xarr[k] < N && j + yarr[k] >= 0 && j + yarr[k] < M)
                        if (arr[i + xarr[k]][j + yarr[k]] != '*')
                            adj[convert(i, j)].push_back(convert(i + xarr[k], j + yarr[k]));
            }
}
 
void aroundSearch(int x, int y)
{
    if (arr[x][y] == '.')
    {
        canGo.push(convert(x, y));
        visit[x][y] = true;
    }
    else if (arr[x][y] >= 'a' && arr[x][y] <= 'z')
    {
        canGo.push(convert(x, y));
        visit[x][y] = true;
        key[arr[x][y] - 'a'] = true;
        while (!door[arr[x][y] - 'a'].empty())
        {
            canGo.push(door[arr[x][y] - 'a'].front());
            visit[back(door[arr[x][y] - 'a'].front()).first][back(door[arr[x][y] - 'a'].front()).second] = true;
            door[arr[x][y] - 'a'].pop();
        }
    }
    else if (arr[x][y] >= 'A' && arr[x][y] <= 'Z')
    {
        if (key[toSmall(arr[x][y]) - 'a'])
        {
            canGo.push(convert(x, y));
            visit[x][y] = true;
        }
        else
            door[arr[x][y] - 'A'].push(convert(x, y));
    }
    else if (arr[x][y] == '$')
    {
        canGo.push(convert(x, y));
        visit[x][y] = true;
        ++ans;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int C;
    cin >> C;
 
    for (int tn = 0; tn < C; ++tn)
    {
        init();
 
        for (int i = 0; i < N; ++i)
        {
            if(!visit[i][0])
                aroundSearch(i, 0);
            if(!visit[i][M-1]) 
                aroundSearch(i, M - 1);
        }    
        for (int i = 0; i < M; ++i)
        {
            if(!visit[0][i])
                aroundSearch(0, i);
            if(!visit[N-1][i])
                aroundSearch(N - 1, i);
        }
        
        while(!canGo.empty())
        {
            int x = back(canGo.front()).first;
            int y = back(canGo.front()).second;
            for(int i = 0; i<4; ++i)
                if(x + xarr[i] >= 0 && x + xarr[i] < N && y + yarr[i] >= 0 && y + yarr[i] < M)
                    if(!visit[x+xarr[i]][y+yarr[i]])
                        aroundSearch(x+xarr[i], y+yarr[i]);
            canGo.pop();
        }
        cout << ans << "\n";
    }
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/9328

9328번: 열쇠

 

 

 

 

 

 

열쇠

그래프로 모델링한후, 열쇠를 주었을때, 문을 발견했을때 등등 각각의 경우에 맞추어 구현하는 문제입니다.