1941번 소문난 칠공주

 백트래킹 문제.

 

 1. 5x5로 25개 고정이므로 25명 중 7명을 고른다. (6603번 로또 참고, https://www.acmicpc.net/problem/6603).

 2. 7명 중 이다솜파(S)가 4명 이상인지 확인한다.

 3. 이다솜파가 4명 이상이면 7명이 붙어있는지 확인한다(BFS).

 

참고)

 

x의 좌표 => 해당 숫자/5

y의 좌표 => 해당 숫자%5

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <queue>
#define visited true
#define Non_visited false
#define MAX 6
 
using namespace std;
 
typedef pair<int,int> pir;
char girls[MAX][MAX];
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
int map[MAX][MAX];
bool v[MAX][MAX];
int order[7];
int store[26];
vector<int> vec;
queue<pir> q;
int ans;
 
 
bool Attachedchecked(){
    int cnt=1;
    
    while(!q.empty()){
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx=x+xx[i];
            int ny=y+yy[i];
            
            if(nx<0 || ny<0 || nx>=5 || ny>=5) continue;
            if(!v[nx][ny] && map[nx][ny]==1){
                v[nx][ny]=visited;
                cnt++;
                q.push(pir(nx,ny));
            }
        }
    }
    
    if(cnt==7){
        return true;
    }
    else{
        return false;
    }
    
}
 
bool Schecked(){
    int cnt=0;
    
    for(int i=0;i<7;i++){
        int x=vec[i]/5;
        int y=vec[i]%5;
        
        if(girls[x][y]=='S'){
            cnt++;
        }
        
        if(cnt>=4){
            q.push(pir(x,y));
            v[x][y]=visited;
            return true;
        }
    }
    
    return false;
}
 
void Clear(){
    
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            map[i][j]=0;
            v[i][j]=Non_visited;
        }
    }
    
    while(!q.empty()){
        q.pop();
    }
    
    while(!vec.empty()){
        vec.pop_back();
    }
}
 
void Combination(int step, int cnt){
    if(cnt==7){
        
        for(int i=0;i<7;i++){
            vec.push_back(order[i]);
        }
        
        if(Schecked()){
            for(int i=0;i<7;i++){
                int x=vec[i]/5;
                int y=vec[i]%5;
                
                map[x][y]=1;
            }
            
            if(Attachedchecked()){
                ans++;
            }
        }
        
        Clear();
        
        return;
    }
    else{
        for(int i=step;i<25;i++){
            order[cnt]=store[i];
            Combination(i+1, cnt+1);
        }
    }
}
 
int main(){
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            cin >> girls[i][j];
        }
    }
    
    for(int i=0;i<25;i++){
        store[i]=i;
    }
    
    Combination(0, 0);
    
    cout << ans << endl;
}