1941 소문난 칠공주

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

C(25,7)=480700가지의 모든 경우를 만들고 BFS로 7명이 인접해 있고 S가 4명 이상인지 확인한다.

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
 
char map[5][6];
bool visit[5][5];
int ans,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
 
bool bfs(int sx,int sy)
{
    int cnt=0,s=0;
    bool check[5][5];
    memset(check,0,sizeof(check));
    queue<pair<int,int>> q;
    check[sx][sy]=true,q.push({sx,sy});
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        cnt++,q.pop();
        if(map[x][y]=='S') s++;
        for(int i=0;i<4;i++)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<0 || nx>=5 || ny<0 || ny>=5 || check[nx][ny] || !visit[nx][ny])
                continue;
            check[nx][ny]=true,q.push({nx,ny});
        }
    }
    return cnt==7 && s>=4;
}
 
bool possible()
{
    for(int i=0;i<5;i++) for(int j=0;j<5;j++)
        if(visit[i][j]) return bfs(i,j)?true:false;
}
 
void go(int x,int y,int cnt)
{
    if(cnt==7)
    {
        if(possible()) ans++;
        return;
    }
    for(int i=x;i<5;i++)
    {
        for(int j=0;j<5;j++)
        {
            if(i==x && j<y) continue;
            visit[i][j]=true;
            if(j!=4) go(i,j+1,cnt+1);
            else go(i+1,0,cnt+1);
            visit[i][j]=false;
        }
    }
}
 
int main()
{
    for(int i=0;i<5;i++) scanf("%s",map[i]);
    go(0,0,0);
    printf("%d",ans);
    return 0;
}