Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

麻烦大牛们看看!(测试数据已过)感激不尽!

Posted by onon at 2006-10-04 12:58:20 on Problem 1088
#include<iostream.h>
#include<stdlib.h>

typedef struct{
     int x;
	 int y;
	 int h;
	 int len;
}Type;

int zone[102][102];
int R, C;
Type z[10004];
int n, max_len;

int local_max(int i);

void read_data()
{
   int i, j;
   
   n = 0;
   cin >> R >> C;
   for(i = 0; i < R; i++)
     for(j = 0; j < C; j++){
	    cin >> zone[i][j];
		z[n].h = zone[i][j];
		z[n].x = j;
		z[n].y = i;
		z[n].len = 0;
		n++;
	 }
}

int cmp(const void *a, const void *b)
{
    int t = (*(Type*)a).h - (*(Type*)b).h;
	  
	if(t > 0) return 1;
	else if(t == 0) return 0;
	else  return -1;
}

void display()
{
	for(int i = 0; i < n; i++)
		 cout << z[i].h << ' ' <<z[i].len << ' ' << endl;
}

void find()
{
   int i, pos;
   z[0].len = 1;

   for( i = 1; i < n; i++){
	  pos = local_max(i);
	  if(pos == -1) z[i].len = 1;
	  else z[i].len = z[pos].len + 1;
   }
}

int local_max( int j)
{
    int m0, n0, m1, n1, m2, n2, m3, n3;
	int len1, len2, len3, len4;
	int L1, L2, L;
    int pos1 = -1, pos2 = -1, pos3 = -1, pos4 = -1;
    int p1, p2, p3;
	int k;

	m0 = z[j].x - 1; n0 = z[j].y;
	m1 = z[j].x + 1; n1 = z[j].y;
	m2 = z[j].x;     n2 = z[j].y - 1;
	m3 = z[j].x;     n3 = z[j].y + 1;
    

	if(m0 >= 0){
		for( k = 0; k < j; k++)
			if(z[k].h == zone[n0][m0] && z[k].h != z[j].h){
				 len1 = z[k].len;
				 pos1 = k;
			     break;
			}
		if(k == j) len1 = 0;
	}
	

	if(m1 < C){
        for( k = 0; k < j; k++)
			if(z[k].h == zone[n1][m1] && z[k].h != z[j].h){
		        len2 = z[k].len;
				pos2 = k;
			    break;
			}
	    if(k == j) len2 = 0;
	}
	

	if(n2 >= 0){
		for( k = 0; k < j; k++)
			if(z[k].h == zone[n2][m2] && z[j].h != z[k].h ){ 
				len3 = z[k].len;
				pos3 = k;
				break;
			}
	    if(k == j) len3 = 0;
	}
	
	if(n3 < R){
		 for( k = 0; k < j; k++)
			 if(z[k].h == zone[n3][m3] && z[k].h != z[j].h){
				  len4 = z[k].len;
				  pos4 = k;
				  break;
			 }
		  if(k == j) len4 = 0;
	}
    
	if(len1 > len2){
		p1 = pos1;
		L = len1;
	}
	else{
		p1 = pos2;
		L = len2;
	}
	if(len3 > len4){
		p2 = pos3;
		L1 = len3;
	}
	else{
		p2 = pos4;
		L1 = len4;
	}
    
	if(L > L1) return p1;
	else if(L < L1) return p2;
	
	if(L == L1 && L == 0) return -1;
}

void solve()
{
	 int i;
     
	 max_len = 0;
	 for(i = 0; i < n; i++){
		  if(z[i].len > max_len) max_len = z[i].len;
	 }
}

		
int main()
{
   

   read_data();
   qsort(z, n, sizeof(Type), cmp);
   find();
   solve();
   display();
   cout << max_len << endl;
  
   return 0;
}
  

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator