#include<iostream>
#include<algorithm>
using namespace std;
int r,c;
int mat[100][100];
bool finish;

struct point{
	int x,y;
}d[4]={{0,-1},{1,0},{0,1},{-1,0}},a[4],b[10000];

int num;
int res,tres;

bool tmp(const point & p1,const point & p2)  
{
	return  mat[p1.x][p1.y]>mat[p2.x][p2.y];
}
void traceback(int x,int y,int k)
{
	if(finish)return;
	int len=0;
	int i;
	for(i=0;i<4;i++)
	{
		if(x+d[i].x>=0&&x+d[i].x<=r-1&&y+d[i].y>=0&&y+d[i].y<=c-1)
		{
			if(mat[x+d[i].x][y+d[i].y]<mat[x][y])
			{
				a[len].x=x+d[i].x;a[len].y=y+d[i].y;
				len++;
			}
			//a[len].h=mat[a[len].x][a[len].y];
		}
	}
	if(!len)
	{
		tres=tres>k?tres:k;
        if(tres==r*c)finish=true;
		return;
	}
	sort(a,a+len,tmp);
	for(i=0;i<len;i++)
	{
		x=a[i].x;y=a[i].y;
		traceback(x,y,k+1);
	}
}

int main()
{
	num=0;
	int x=0,y=0;
	int i,j;
	cin>>r>>c;
	for(i=0;i<r;i++)
	{
		for(j=0;j<c;j++)
		{
			cin>>mat[i][j];
			b[num].x=i;
			b[num].y=j;
			num++;
		}
	}
	sort(b,b+num,tmp);
	finish=false;
	traceback(b[0].x,b[0].y,1);
	res=tres;
	if(res==r*c)
	{
		cout<<res<<endl;
		return 0;
	}
 	for(i=1;i<num;i++)
	{
		finish=false;
		tres=0;traceback(b[i].x,b[i].y,1);
		res=res>tres?res:tres;
	}
    cout<<res<<endl;
	return 0;
}

	

• Re:暴搜过的，附上代码。。。 (1466) ysjjovo 2010-09-08 22:00:38
  • 先前用暴搜32MS，，，后来改dp却变47MS 郁闷.. (978) ysjjovo 2010-09-08 22:03:09
    • Re:先前用暴搜32MS，，，后来改dp却变47MS 郁闷.. (14) drcrow 2010-11-25 20:22:58