#include <iostream>

using namespace std;

int arr[101][101]={0};
	int brr[101][101][2]={0};
	int crr[101][101][2]={0};
int f(int x,int y,int ji)
{
	int com=-1;int count=0;int tem=(ji-1)%2;
	if(arr[x][y]<arr[x-1][y]&&crr[x-1][y][tem]==0)
	{
		if(com<brr[x-1][y][tem])
			com=brr[x-1][y][tem];
		++count;
	}
	if(arr[x][y]<arr[x+1][y]&&crr[x+1][y][tem]==0)
	{
		if(com<brr[x+1][y][tem])
			com=brr[x+1][y][tem];
		++count;
	}
	if(arr[x][y]<arr[x][y-1]&&crr[x][y-1][tem]==0)
	{
		if(com<brr[x][y-1][tem])
			com=brr[x][y-1][tem];
		++count;
	}
	if(arr[x][y]<arr[x][y+1]&&crr[x][y+1][tem]==0)
	{
		if(com<brr[x][y+1][tem])
			com=brr[x][y+1][tem];
		++count;}
	
	if(count)
	{
		brr[x][y][ji%2]=com+1;
		return 0;
	}else
	{
		crr[x][y][ji%2]=1;
		return 1;
		
	}
}

int main()
{
	
	
	int r,c;
	cin>>r>>c;
	int sum=r*c;
	for(int wo=1;wo<=r;++wo)
	{
		for(int ni=1;ni<=c;++ni)
		{
			cin>>arr[wo][ni];
		}
	}
	int ji=1;
	for(ji=1;;++ji)
	{
		for(int i=1;i<=r;++i)
		{
			for(int j=1;j<=c;++j)
			{
				if(crr[i][j][(ji-1)%2])
					continue;
				sum-=f(i,j,ji);
				
				if(sum==0)
				{
					cout<<ji<<endl;
					return 0;
				}
				
			}
		}
		for(int cc=1;cc<=r;++cc)
			for(int dd=1;dd<=c;++dd)
			{
				crr[cc][dd][(ji-1)%2]=crr[cc][dd][ji%2];
			}
	}



	
}

• Re:求牛人看看 动态规划超时 (186) derambroken 2007-10-15 17:52:24
  • Re:求牛人看看 动态规划超时 (8) niuniu2006 2007-10-17 12:41:52
• Re:求牛人看看 动态规划超时 (37) cagy 2007-10-24 19:27:50
  • Re:求牛人看看 动态规划超时 (73) niuniu2006 2008-04-01 21:25:54
• 这个怎么超时了？怎么缩减？ (738) zhao12312344 2007-10-27 17:04:08