[백준] 10767 Palindromic Paths

(0,0) ~ (n-1,n-1) 까지 가는 팰린드롬 경로를 찾는 문제다

처음에 중복을 다 세는 줄 알고 dp로 짰는데 수가 넘 컸다..

그래서 다 지우고 bfs 돌렸다가 틀렸따... 그냥 돌리면 메모리 초과다

팰린드롬이려면 대각선까지 가는것만 보면 된다

그래서 대각선 정점마다 set을 만들어 (0,0)에서 출발해서 set에 넣고

(n-1,n-1)에서 출발해서 set에 있는지 보면 된다

소스코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <set>
using namespace std;
int n;
char arr[22][22];
set<string> sarr[444], ans;
void f(int x, int y,string s) {
    if (s.size() == n) {
        sarr[x*y + y].insert(s); return;
    }
    if(x+1<n) f(x + 1, y, s + arr[x + 1][y]);
    if (y + 1 < n) f(x, y + 1, s + arr[x][y + 1]);
}
void sf(int x, int y, string s) {
    if (s.size() == n) {
        if (sarr[x*y + y].count(s)) ans.insert(s);
        return;
    }
    if (x - 1 >= 0) sf(x - 1, y, s + arr[x - 1][y]);
    if (y - 1 >= 0) sf(x, y - 1, s + arr[x][y - 1]);
}
int main() {
    scanf(" %d", &n);
    for (int i = 0; i < n; i++) scanf(" %s", &arr[i]);
    string s = "";
    s += arr[0][0];
    f(0, 0, s);
    s = "";
    s += arr[n - 1][n - 1];
    sf(n - 1, n - 1, s);
    printf("%d\n", ans.size());
}