I. 试题I：对称迷宫 25’
描述

用EXCEL求解迷宫真香~

wlxsq有一个N∗NN*NN∗N的网格迷宫，每一个网格都有一个字母编号。

他要从左上角(1,1)(1,1)(1,1)出发，走到右下角(n,n)(n,n)(n,n)，由于wlxsq很懒，所以他每次只会往右或者往下走一格。

由于最后到终点的路径方案太多太多了，所以wlxsq想让你计算出所有不同的对称的路径个数。

例如:N=3N = 3N=3

ABA

BBB

ABA

对称路径6条：有ABABA(2条)、ABBBA(4条)

不同的对称路径有: 有ABABA、ABBBA
输入

第一行输入一个数NNN，表示迷宫的大小。

接下来输入N∗NN*NN∗N的字母迷宫
输出

输出对称路径的数量
样例
输入
复制

3
ABA
BBB
ABA

输出
复制

2

提示

【评测用例规模与约定】

对于40%40%40%的数据，2<=N<=112<=N<=112<=N<=11

对于100%100%100%的数据，2<=N<=182<=N<=182<=N<=18
之前做的时候题目理解错了，我以为路径不对称只要字符串相等就可以，结果要对称，如果纯暴力的2的18次会超时

#include<bits/stdc++.h>
using namespace std;
char a[25][25];
bool st[25][25]; int dir[2][2]={
   {
   0,1},{
   1,0}}; int dir2[2][2]={
   {
   0,-1},{
   -1,0}};
map<string,int>mp[25];
map<string,int>T;
	int n;
	int ans; void dfs2(int x,int y,string s)
{
   
	s+=a[x][y]; if(x+y==n-1)
	{
   
		if(!T[s]&&mp[x][s]==1)//如果这种走法没被选过的话并且这种走法在dfs1里面可行，走法多一种
		{
   
			ans++;
			T[s]=1;
		}
		return;
	}
	for(int i=0;i<2;i++)
	{
   
		int tx=x+dir2[i][0];
		int ty=y+dir2[i][1];
		if(tx<0||ty<0||tx>=n||ty>=n)	continue; if(!st[tx][ty])
		{
   
		st[tx][ty]=1;
		dfs2(tx,ty,s);
		st[tx][ty]=0;
		}
	}
}
void dfs(int x,int y,string ss)
{
   
	ss+=a[x][y]; if(x+y==n-1)//x和y在对角线上的时候
	{
   
		mp[x][ss]=1;
		return ;
	 } 
	for(int i=0;i<2;i++)
	{
   
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(tx<0||ty<0||tx>=n||ty>=n)	continue; if(!st[tx][ty])
		{
   
			st[tx][ty]=1;
			dfs(tx,ty,ss);
			st[tx][ty]=0;
		 } 
	}
}
int main()
{
   

	cin>>n;
	for(int i=0;i<n;i++)
	scanf("%s",a+i);
	dfs(0,0,"");
	dfs2(n-1,n-1,"");
	cout<<ans<<endl;
 }