题意： 给你一个n*m的字符矩阵，问你从（1，1）走到（n,m）有多少种方法是经过的字符串是回文，只能向右或是向下走
dp[][i][j] i j 代表的是目前走到的两个点的横坐标 使得（1,1）->（i,y1） (n,m)->(j,y2) 得到的串相同的方法数
#include<bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; char p[510][510]; long long dp[2][510][510]; int dir[4][2]={1,0,0,1,0,-1,-1,0}; int n,m; void add(long long &a,long long b){ a+=b; if(a>=mod) a-=mod; } bool judge(int x,int y){ if(x>=0&&x<n&&y>=0&&y<m) return 1; return 0; } long long solve(){ if(p[0][0]!=p[n-1][m-1]) return 0; if(n==1&&m==1) return 1; int cur,nex; memset(dp,0,sizeof(dp)); dp[0][0][n-1]=1; //dp[0][i][j] 枚举两个点的横坐标 int num; if((n+m-1)&1) num=(n+m-2)/2; else num=(n+m-1)/2-1; for(int i=0;i<num;i++){ cur=i&1; nex=cur^1; for(int j=0;j<n;j++) for(int k=0;k<n;k++) if(dp[cur][j][k]){ int x1,y1,x2,y2; x1=j;y1=i-j; x2=k;y2=m-1-(i-(n-1-k)); for(int ii=0;ii<2;ii++){ int xx1=x1+dir[ii][0]; int yy1=y1+dir[ii][1]; if(!judge(xx1,yy1)) continue; for(int jj=2;jj<4;jj++){ int xx2=x2+dir[jj][0]; int yy2=y2+dir[jj][1]; if(!judge(xx2,yy2)) continue; if(xx1>xx2||yy1>yy2) continue; if(p[xx1][yy1]==p[xx2][yy2]) add(dp[nex][xx1][xx2],dp[cur][j][k]); } } dp[cur][j][k]=0; } } long long ans=0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) add(ans,dp[num&1][i][j]); return ans; } int main(){ while(cin>>n>>m){ for(int i=0;i<n;i++) scanf("%s",p[i]); printf("%lld ",solve()); } }