bfs + 线段覆盖

#include
     
      using namespace std;struct sea {    int h , num;    bool got;} s[500];bool cmp( sea a , sea b ) {    return a.h > b.h;}const int dir[4][2] = { { 0 , 1 } , { 0 , -1 } , { 1 , 0 } , { -1 , 0 } };int ma[500][500] , n , m , ans , ct[501];bool built[501];queue
      
        desert[500];void bfs( int start ) {    bool went[500][500] = { 0 };    queue
       
        
          > q;    q.push( make_pair( 0 , start ) );    if( n == 1 ) {        desert[start].push( start );        ct[start]++;    }    while( !q.empty() ) {        pair
         
           a = q.front();        q.pop();        for( int i = 0 ; i < 4 ; i++ ) {            pair
          
            b = make_pair( a.first + dir[i][0] , a.second + dir[i][1] ); if( b.first >= 0 && b.first < n && b.second >= 0 && b.second < m && went[b.first][b.second] == 0 && ma[b.first][b.second] < ma[a.first][a.second] ) { q.push( b ); if( b.first == 0 ) s[b.second].got = 1; if( b.first + 1 == n ) { desert[b.second].push( start ); ct[start]++; } went[b.first][b.second] = 1; } } }}void greedy() { int i = 0; while( i < m ) { int maxnum = 0 , maxn; while( !desert[i].empty() ) { ct[desert[i].front()]--; if( ct[desert[i].front()] >= maxnum ) { maxnum = ct[desert[i].front()]; maxn = desert[i].front(); } desert[i].pop(); } i++; while( ct[maxn] > 0 ) { while( !desert[i].empty() ) { ct[desert[i].front()]--; desert[i].pop(); } i++; } ans++; }}int main() { cin >> n >> m; for( int i = 0 ; i < n ; i++ ) for( int j = 0 ; j < m ; j++ ) cin >> ma[i][j]; for( int i = 0 ; i < m ; i++ ) s[i].h = ma[0][i] , s[i].num = i , s[i].got = 0; sort( s , s + m , cmp ); int p = 0; while( p < m ) { if( !s[s[p].num].got ) bfs( s[p].num ); p++; } for( int i = 0 ; i < m ; i++ ) if( desert[i].empty() ) ans++; if( ans != 0 ) { cout << 0 << '\n' << ans; return 0; } greedy(); cout << 1 << '\n' << ans;}