1941] 소문난 칠공주

문제 설명

:  5x5 배열에서 길이가 7 경로 중 'S'를 4개 이상 포함한 경로의 개수를 구하는 문제.

단순히 dfs처럼 보이지만, 십자가 모양의 경로 같은 경우는 dfs로 구현해내기가 어렵다. (사실 잘 모르겠다)

5x5 배열이기 때문에 (0,0)..... (4,4)를 각각 출발점으로 삼는 경로를 모두 만들어내어 'S'가 4개 이상인 경우만 체크해주면 쉽게 해결이 된다. 

현재 경로를 저장하는 stat과 1<<i 와의 &연산으로 인접한 경로로만 갈 수 있도록 한다.

문제링크 [1941 : 소문난 칠공주]

소스 코드

#include <stdio.h>
using namespace std;
const int ud[4] = { 0,0,1,-1 };
const int lr[4] = { -1,1,0,0 };
char ary[5][6];
int res;
bool chk[1 << 25];
void dfs(int cnt, int scnt,int stat)
{
    chk[stat] = true;
    if (cnt >= 7) {
        if (scnt >= 4)res++;
        return;
    }
    for (int i = 0; i < 25; i++) {
        if (!(stat&(1 << i)))continue;
        int x = i / 5, y = i % 5;
        for (int w = 0; w < 4; w++) {
            int _x = x + ud[w], _y = y + lr[w];
            if (_x < 0 || _x > 4 || _y < 0 || _y > 4)continue;
            if (stat&(1 <<(_x * 5 + _y)) || chk[stat|(1<<(_x*5+_y))])continue;
            dfs(cnt + 1, scnt + (ary[_x][_y] == 'S'), stat | (1 << (_x * 5 + _y)));
        }
    }
}
 
int main()
{
    for (int i = 0; i  <  5; i++)scanf("%s", ary[i]);
    for (int i = 0; i  <  5; i++)
        for (int j = 0; j  <  5; j++)
            dfs(1, ary[i][j] == 'S',(1<<(i*5+j)));
 
    printf("%d\n", res);
    return 0;
}