모든 좌표를 순회하면서 DFS로 풀이하려고 하였지만 방향이 여러군데로 퍼지있는 모양을 찾는 구현을 하지 못하였다.
예를들어 이런 경우
00000
00100
11110
01010
00000
그래서 다시 생각해보니 전체 크기가 5*5 밖에 되지 않기 때문에 25C7 연산도 값이 그렇게 크지 않을 것이라고 생각되었다.
전체에서 7개를 무작위롤 뽑은 뒤 Y가 3개 이하로 포함되어 있으면서 서로 접해있는 경우를 찾으면 정답을 얻을 수 있었다.
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };
using namespace std;
string arr[5];
set<pair<int, int>> s;
int ans = 0;
void solve(vector<int>& v) {
set<int> temp;
for (int x : v) temp.insert(x);
queue<int> q;
bool visited[5][5] = { false, };
q.push(v[0]);
visited[v[0] / 5][v[0] % 5] = true;
int cnt = 1;
while (!q.empty()) {
int x = q.front() % 5;
int y = q.front() / 5;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5 || visited[ny][nx]) continue;
else if (temp.count(ny * 5 + nx) == 1) {
visited[ny][nx] = true;
cnt++;
q.push({ ny * 5 + nx });
}
}
}
if (cnt == 7) ans++;
}
void permutation(int d, vector<int>& v) {
int len = v.size();
if (len >= 4) {
int c = 0;
for (int i = 0; i < len; i++) {
int x = v[i] % 5;
int y = v[i] / 5;
if (s.count({ x ,y }) == 0) c++;
}
if (c >= 4) return;
}
if (len == 7) {
solve(v);
return;
}
else if (d == 25) return;
else {
v.push_back(d);
permutation(d + 1, v);
v.pop_back();
permutation(d + 1, v);
}
}
int main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
for (int i = 0; i < 5; i++) {
cin >> arr[i];
for (int j = 0; j < 5; j++) {
if (arr[i][j] == 'S') s.insert({ j, i }); // x y
}
}
vector<int> t;
permutation(0, t);
cout << ans;
return 0;
}