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

测了这里所有的数据都没问题,但就是WA。。。抓狂。。。牛人指点!

Posted by FailedWing at 2007-03-06 23:42:48 on Problem 1088
#include<iostream>
#include<algorithm>

using namespace std;

int r, c;
long ans;
long map[102][102], f[101][101];
int op[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
long total = 0;
struct node
{
       long x, y, h;
}      que[10000];

int comp(node a, node b)
{
    return a.h < b.h;
}

void init()
{
     ans = 1;
     for (int i = 0; i != r + 2; i ++)
     {
         map[i][0] = map[i][c + 1] = 10001;
     }
     for (int i = 0; i != c + 2; i ++)
     {
         map[0][i] = map[r + 1][i] = 10001;
     }
     for (int i = 1; i != r + 1; i ++)
         for (int j = 1; j != c + 1; j ++)
         {
             scanf("%d", &map[i][j]);
             que[total].x = i;
             que[total].y = j;
             que[total].h = map[i][j];
             f[i][j] = -1;
             total ++;
         }
}

void make(int x, int y)
{
     f[x][y] = 1;
     for (int i = 0; i != 4; i ++)
         if (map[x + op[i][0]][y + op[i][1]] > map[x][y])
         {
            if (f[x + op[i][0]][y + op[i][1]] == -1)
               make(x + op[i][0],y + op[i][1]);
            f[x][y] = max(f[x][y], f[x + op[i][0]][y + op[i][1]] + 1);
            if (f[x][y] > ans)
               ans = f[x][y];
         }
}

void fill_in()
{
     for (int i = 0; i != total; i ++)
         if (f[que[i].x][que[i].y] == -1)
            make(que[i].x, que[i].y);
}

void print()
{
     printf("%d\n", ans);
}

int main()
{
    while (scanf("%d%d", &r, &c) != -1)
    {    
          init();
          sort(que, que + total, comp);
          fill_in();
          print();
    }
}

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