> #include <iostream>
> 
> using namespace std;
> int m,n;
> struct node 
> {
> 	int N;
> 	int l,r;
> };
> void copy(node &a,node &b)
> {
> 	a.N=b.N;a.l=b.l;a.r=b.r;
> }
> int Partition(node a[],int low,int high)
> {
>     int pivotloc;
> 	copy(a[0],a[low]);
> 	pivotloc=a[low].N;
> 	while(low<high)
> 	{
> 		while(low<high&&a[high].N>=pivotloc)
> 			--high;
> 		if(low<high){
> 			copy(a[low++],a[high]);
> 		}
> 		while(low<high&&a[low].N<=pivotloc)
> 			++low;
> 		if(low<high)
> 		{
> 			copy(a[high--],a[low]);
> 		}
> 	}
> 	copy(a[low],a[0]);
> 	return low;
> }
> void QSort(node a[],int s,int t)
> {   
>     int pivotloc;
> 
> 	if(s<t){
> 	 pivotloc=Partition(a,s,t);
> 	 QSort(a,s,pivotloc-1);    
> 	 QSort(a,pivotloc+1,t);
> 	}
> }
> void Quick_sort(node a[])
> {
>   QSort(a,1,m*n);
> 
> }
> int  main()
> {
> 	int **a,i,j,k=1,*visted;
> 	node *b;
> 	int c[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
> 	cin>>m>>n;
>     a=new int*[m+2];
> 	for(i=0;i<m+2;i++)
> 		a[i]=new int[n+2];
> 	b=new node[m*n+1];
> 	visted=new int[m*n+1];
> 	for(i=1;i<=m*n;i++)
> 		visted[i]=1;
> 	for(i=1;i<=m;i++)
> 		for(j=1;j<=n;j++)
> 		{
> 			cin>>a[i][j];
> 		}
> 	for(i=1;i<=m;i++)
> 		for(j=1;j<=n;j++)
> 		{  
> 			b[k].N=a[i][j];
> 			b[k].l=i;
> 			b[k].r=j;
> 			k++;
> 		}	
> 	Quick_sort(b);
> 	int sum=0,count=1;
> 	node p;k=1;
> 	for(k=1;k<=m*n-sum;k++) 
> 	{  
>     	if(visted[k])
> 		{
> 	     copy(p,b[k]);visted[k]=0;
> 	    for(i=k+1;i<=m*n;i++)
> 		{   
> 		    for(j=0;j<4;j++)
> 			if((p.l+c[j][0])>=1&&(p.l+c[j][0])<=m&&(p.r+c[j][1])>=1&&(p.r+c[j][1])<=n&&
> 				a[p.l+c[j][0]][p.r+c[j][1]]==b[i].N&&b[i].N>p.N)
> 			{  
> 			   count++;	
> 			   p.N=p.l=p.r=0;
> 			   copy(p,b[i]);
> 			   visted[i]=0;
> 			   break;
> 			}
> 		}
>     	 if(count>sum)sum=count; 	 
> 		}
> 	count=1;
> 	}
> 	cout<<sum<<endl;
> 	return 0;
> }

• Re:用记忆化搜索好做 (78) boys 2006-07-23 11:27:15