> #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;
> }
> 
> 	

• 先前用暴搜32MS，，，后来改dp却变47MS 郁闷.. (978) ysjjovo 2010-09-08 22:03:09
  • Re:先前用暴搜32MS，，，后来改dp却变47MS 郁闷.. (14) drcrow 2010-11-25 20:22:58