반응형
// 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;
}
/*
*/
반응형