$双向搜索题目$

$第一遍dfs从(1,1)开始搜索到中点(x+y=1)出，并将路径保存到路径1方案中$

$然后再从(n,n)跑到中点，保存路径2$

$最后枚举路径1中的路径是否在路径2中出现，且中点一样$

$不能只使用一个map，因为要保证中点一样，还要再开一个记录位置$

#include<bits/stdc++.h>
using namespace std;

const int N=20;

map<string,int> mp;
map<string,int> st[N];
int res;
char a[N][N];  //注意char类型 
int n;

void dfs1(int x,int y,string s){
    if(x+y==n+1){
        mp[s]=1; 
        st[x][s]=1;  //标记是到（x，n-x)的到字符串s 
        return;
    }
    if(x<n) dfs1(x+1,y,s+a[x+1][y]);  //当前x最大为n-1，因为要递归x+1  
    if(y<n) dfs1(x,y+1,s+a[x][y+1]); //一般都会先把下一项加上，递归边界不用在处理 
}

void dfs2(int x,int y,string s){
    if(x+y==n+1){
        if(mp[s]&&st[x][s]) res++,mp[s]=0;  //只算一次，所以mp[s]=0 //要求这个字符串到达（x，y)形成的s 
        return;
    }
    if(x>1) dfs2(x-1,y,s+a[x-1][y]);
    if(y>1) dfs2(x,y-1,s+a[x][y-1]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }

    dfs1(1,1,"");
    dfs2(n,n,"");
    cout<<res<<endl;
    return 0; 
}