#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

#define N 105

int w,h;
char city[N][N];
int dp[3][N][N];
//这里开dp[2][N][N]会RE，我下面dp数组的第一个下标都是0和1，怎么就会RE呢？真不知是怎么回事，郁闷啊

void DP()
{
	int m,i,j,k,nsteps=w+h-2;
	if(city[0][0]=='*') dp[0][0][0]=1;
	else dp[0][0][0]=0;
	for(k=1;k<=nsteps;k++)
	{
		for(i=0;i<=k;i++)
		{
			for(j=0;j<=k;j++)
			{
				if(city[i][k-i]=='#' || city[j][k-j]=='#')
				{
					dp[1][i][j]=-1;
					continue;
				}
				m=-1;
				if(i<=k-1 && j<=k-1) m=max(m,dp[0][i][j]);
				if(j<=k-1 && i-1>=0) m=max(m,dp[0][i-1][j]);
				if(i<=k-1 && j-1>=0) m=max(m,dp[0][i][j-1]);
				if(i-1>=0 && j-1>=0) m=max(m,dp[0][i-1][j-1]);
				if(m==-1)
				{
					dp[1][i][j]=-1;
					continue;
				}
				dp[1][i][j]=m;
				if(city[i][k-i]=='*') dp[1][i][j]++;
				if(i!=j && city[j][k-j]=='*') dp[1][i][j]++;
			}
		}
		for(i=0;i<=k;i++)
			for(j=0;j<=k;j++)
				dp[0][i][j]=dp[1][i][j];
	}
}

int main()
{
	int cases,i;
	scanf("%d",&cases);
	while(cases--)
	{
		scanf("%d%d",&w,&h);
		for(i=0;i<h;i++)
			scanf("%s",city[i]);
		DP();
		printf("%d\n",dp[1][h-1][h-1]);
	}
return 0;
}

• 擦，我明白了，第一个下标没越界，后面两个越界了，囧啊。。。 (1300) woLaiDaJiangYou 2012-03-09 20:45:17