1941번: 소문난 칠공주

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


$O(1)$

25칸 중 7개의 칸을 선택해서 모두 인접해 있고 S가 4개 이상인 경우를 카운트

#include<cstdio>
#include<algorithm>
using namespace std;
char a[5][6];
const int fx[] = { 0,1,0,-1 }, fy[] = { 1,0,-1,0 };
int r, vis[5][5], p[25], s, tot;
void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= 5 || y >= 5 || vis[x][y] || !p[x * 5 + y]) return;
    vis[x][y] = 1;
    s += a[x][y] == 'S';
    tot++;
    for (int i = 0; i < 4; i++) dfs(x + fx[i], y + fy[i]);
}
int main() {
    for (int i = 0; i < 5; i++) scanf("%s", a[i]);
    for (int i = 18; i < 25; i++) p[i] = 1;
    do {
        fill(vis[0], vis[5], 0);
        int i = s = tot = 0;
        for (; !p[i]; i++);
        dfs(i / 5, i % 5);
        r += tot == 7 && s > 3;
    } while (next_permutation(p, p + 25));
    printf("%d", r);
    return 0;
}