2964-有一个三维的dp.txt

acm 做题和编程时常用的一些算法

#include<stdio.h>
#include<string.h>

#define maxv 100+5

short opt[maxv+maxv][maxv][maxv];
char G[maxv][maxv];
int m, n;

int min(int a, int b){
	return a>b?b:a;
}

void tour()
{
	int i, j, k, p, ma, b, e;
	if(G[0][0]=='#') { opt[m+n-2][n-1][n-1]=0; return; }
	for(i=0; i<m+n-1; i++)	for(j=0; j<n; j++) for(k=0; k<n; k++) opt[i][j][k] = 0
;

	if( G[0][0]=='*' ) opt[0][0][0] = 1;
	p = min(m, n);
	for(i=1; i<m+n-1; i++)
	{
		if( i<m ) b = 0, e = min(i, p);
		else b++, e = min(b+p, n-1);

		for(j=b; j<=e; j++)
		{
			for(k=j; k<=e; k++)
			{
				if( G[j][i-j]=='#'||G[k][i-k]=='#' ) continue;

				ma = opt[i-1][j][k];
				if( j>0 && opt[i-1][j-1][k]>ma ) ma = opt[i-1][j-1][k];
				if( k>0 && opt[i-1][j][k-1]>ma ) ma = opt[i-1][j][k-1];
				if( j>0&&k>0&&opt[i-1][j-1][k-1]>ma ) ma = opt[i-1][j-1][k-1];

				if( G[j][i-j]=='*' ) opt[i][j][k]++;
				if( k!=j && G[k][i-k]=='*' ) opt[i][j][k]++;
				
				opt[i][j][k] += ma;
			}
		}
	}
}

int main()
{
	int cas, i;
	scanf("%d", &cas);
	while( cas-- )
	{
		scanf("%d%d", &m, &n);
		getchar();
		for(i=0; i<n; i++)	gets(G[i]);

		tour();
		printf("%d\n", opt[m+n-2][n-1][n-1]);
	}
	return 0;
}