51nod 1503 猪和回文

dp[step][x1][x2]代表从起点、终点分别走了step步，从起点走到了(x1,step-x1)，从终点走到了(x2,n+m-2-x2-step)时，前后路径对称的总数。

注意特判 mz[0][0]!=mz[n-1][m-1] 的情况，我被坑死了。。。。。

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

const long long mod=1e9+7;
long long dp[2][550][550];
char mz[550][550];
long long n,m;

bool judgex1(long long step,long long x1)
{
	return x1>=max(step-(m-1),(long long)0) && x1<=min(step,n-1);
}

bool judgex2(long long step,long long x2)
{
	return x2>=max((long long)0,n-1-step) && x2<=min(n-1,n+m-2-step);
}

int main()
{
	long long i,j,ans,step,x1,x2;
	while(cin>>n>>m)
	{
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
				scanf(" %c",&mz[i][j]);
		//n-1-x2+m-1-y2=step
		//n+m-2-x2-step 
		//x1+y1=step
		memset(dp,0,sizeof(dp));
		if(mz[0][0]==mz[n-1][m-1])//这一步坑死我了 
			dp[0][0][n-1]=1;
		for(step=1;step<=(n+m-3)/2;step++)
		{
			for(x1=max(step-(m-1),(long long)0);x1<=min(step,n-1);x1++)
			{
				for(x2=min(n-1,n+m-2-step);x2>=max((long long)0,n-1-step);x2--)
				{
					if(mz[x1][step-x1]==mz[x2][n+m-2-x2-step])
					{
						dp[step&1][x1][x2]=0;//还有这里 
						
						if(judgex1(step-1,x1-1)&&judgex2(step-1,x2+1))
							dp[step&1][x1][x2]+=dp[step&1^1][x1-1][x2+1];
							
						if(judgex1(step-1,x1-1)&&judgex2(step-1,x2))
							dp[step&1][x1][x2]+=dp[step&1^1][x1-1][x2];
							
						if(judgex1(step-1,x1)&&judgex2(step-1,x2+1))
							dp[step&1][x1][x2]+=dp[step&1^1][x1][x2+1];
							
						if(judgex1(step-1,x1)&&judgex2(step-1,x2))
							dp[step&1][x1][x2]+=dp[step&1^1][x1][x2]; 
							
						dp[step&1][x1][x2]%=mod;
					}
					else
						dp[step&1][x1][x2]=0;
				}
			}
		}
		ans=0;
		if((n+m)==2)
		{
			ans=1;
		}
		else if((n+m)&1)
		{
			step=(n+m-3)>>1;
			for(i=max(step-(m-1),(long long)0);i<=min(step,n-1);i++)
			{
				if(judgex2(step,i+1))
					ans+=dp[step&1][i][i+1];
				if(judgex2(step,i))
					ans+=+dp[step&1][i][i];
				ans%=mod;
			}
		}
		else
		{
			step=(n+m-4)>>1;
			for(i=max(step-(m-1),(long long)0);i<=min(step,n-1);i++)
			{
				if(judgex2(step,i))
					ans+=dp[step&1][i][i];
				if(judgex2(step,i+1))
					ans+=dp[step&1][i][i+1]*2;
				if(judgex2(step,i+2))
					ans+=dp[step&1][i][i+2];
				ans%=mod;
			}
		} 
		printf("%lld\n",ans);
	} 
}