카테고리 없음

1941

선달 2022. 8. 24. 04:17
반응형
// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

char input[10][10];
vector<pair<int,int>> seat;
bool used[30];
vector<pair<int,int>> prin;
int ans;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

void recur(int doyeon, int tot) {
    if(tot == 7) {
        bool prinPos[5][5] = {}, vis[5][5] = {};
        for(int i=0; i<7; i++) prinPos[prin[i].first][prin[i].second] = true;
        
        queue<pair<int,int>> q;
        q.push({prin[0].first, prin[0].second});
        
        int cntAdj = 0;
        while(!q.empty()) {
            pair<int, int> cur = q.front();
            q.pop();
            cntAdj++;
            
            for(int dir=0; dir<4; dir++) {
                int x = cur.first + dx[dir];
                int y = cur.second + dy[dir];
                
                if(x<0 || x>=5 || y<0 || y>=5) continue;
                if(!prinPos[x][y] || vis[x][y]) continue; // 이미 방문했거나 해당하는 부분이 아닐경우
                
                q.push({x,y});
                prinPos[x][y] = false;
            }
        }
        
        if(cntAdj == 7 && doyeon < 4 ) ans++;
        return;
    }
    
    for(int i=0; i<25; i++){
        int cx = seat[i].first;
        int cy = seat[i].second;
        
        if(!used[i]) {
            prin.push_back({cx,cy});
            used[i] = true;
            
            char ds = input[cx][cy];
            if(ds == 'Y') recur(doyeon+1, tot+1);
            else recur(doyeon, tot+1);
            
            used[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    for(int i=0; i<5; i++) {
        for(int j=0; j<5; j++) {
            seat.push_back({i,j});
            cin >> input[i][j];
        }
    }

    recur(0,0);

    cout << ans;
    
    return 0;
}

/*
 */
반응형