Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
拓扑+宽搜 水过,0MS#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator