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

拓扑+宽搜 水过,0MS

Posted by ouyangwenbin at 2014-03-30 16:43:13 on Problem 1088
#include <cstdio>
#include <cstdlib>
#include <cstring>

struct node
{
    int x, y, next;
}a[220000]; int first[110000], len;

int h[110][110];
int f[11000];
int ru[11000];
int list[11000], head, tail;

void ins ( int x, int y )
{
    len ++;
    a[len].x = x; a[len].y = y;
    a[len].next = first[x]; first[x] = len;
}

int main ()
{
    memset ( h, 63, sizeof(h) );
    int n, m;
    scanf ( "%d%d", &n, &m );
    int i, j;
    for ( i = 1; i <= n; i ++ )
     for ( j = 1; j <= m; j ++ )
      scanf ( "%d", &h[i][j] );

    memset ( first, 0, sizeof(first) ); len = 0;
    memset ( ru, 0, sizeof(ru) );
    for ( i = 1; i <= n; i ++ )
     for ( j = 1; j <= m; j ++ )
     {
        if ( h[i][j] > h[i-1][j] ) ins ( (i-1)*m+j, (i-2)*m+j ), ru[(i-2)*m+j]++;
        if ( h[i][j] > h[i+1][j] ) ins ( (i-1)*m+j, (i)*m+j ), ru[(i)*m+j]++;
        if ( h[i][j] > h[i][j-1] ) ins ( (i-1)*m+j, (i-1)*m+j-1 ), ru[(i-1)*m+j-1]++;
        if ( h[i][j] > h[i][j+1] ) ins ( (i-1)*m+j, (i-1)*m+j+1 ), ru[(i-1)*m+j+1]++;
     }

    for ( i = 1; i <= n*m; i ++ ) f[i] = 1;
    head = 1; tail = 1;
    for ( i = 1; i <= n*m; i ++ )
     if ( ru[i] == 0 ) list[tail++] = i;
    while ( head <= n*m )
    {
        int x = list[head];
        for ( int k = first[x]; k; k = a[k].next )
        {
            int y = a[k].y;
            if ( f[x]+1 > f[y] ) f[y] = f[x]+1;
            if ( --ru[y] == 0 ) list[tail++] = y;
        }
        head ++;
    }

    int ans = 0;
    for ( i = 1; i <= n*m; i ++ )
     if ( f[i] > ans ) ans = f[i];
    printf ( "%d\n", ans );
    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