P1514-引水入城

系统管理员 2023-06-01 08:48 4阅读 0赞

1 #include <bits/stdc++.h>
      2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
      3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
      4 #define INF 0x3f3f3f3f
      5 typedef long long ll;
      6 using namespace std;
      7 inline ll read()
      8 {
      9     ll ans = 0;
     10     char ch = getchar(), last = ' ';
     11     while(!isdigit(ch)) last = ch, ch = getchar();
     12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
     13     if(last == '-') ans = -ans;
     14     return ans;
     15 }
     16 inline void write(ll x)
     17 {
     18     if(x < 0) x = -x, putchar('-');
     19     if(x >= 10) write(x / 10);
     20     putchar(x % 10 + '0');
     21 }
     22 struct section
     23 {
     24     int l;
     25     int r;
     26     bool operator < (section b)
     27     {
     28         if(l != b.l)
     29             return l < b.l;
     30         return r > b.r;
     31     }
     32 };
     33 
     34 int N,M;
     35 int a[503][503];
     36 section dp[503][503];
     37 bool vis[503][503];
     38 bool ok[503];
     39 int dx[] = {
        1,-1,0,0};
     40 int dy[] = {
        0,0,1,-1};
     41 
     42 bool valid(int x,int y)
     43 {
     44     return x>=1 && y>=1 && x<=N && y<=M;
     45 }
     46 
     47 void bfs()
     48 {
     49     queue<pair<int,int>> q;
     50     int arr[503][503];
     51     memset(arr,0,sizeof(arr));
     52     _for(i,1,M+1)
     53     {
     54         arr[1][i] = 1;
     55         q.push({
        1,i});
     56     }
     57     while(!q.empty())
     58     {
     59         pair<int,int> p = q.front();
     60         q.pop();
     61         if(p.first==N)
     62             ok[p.second] = 1;
     63         _for(i,0,4)
     64         {
     65             int nx = p.first+dx[i];
     66             int ny = p.second+dy[i];
     67             if(valid(nx,ny) && !arr[nx][ny] && a[nx][ny] < a[p.first][p.second])
     68             {
     69                 arr[nx][ny] = 1;
     70                 q.push({nx,ny});
     71             }
     72         }
     73     }
     74 }
     75 section dfs(int x,int y)
     76 {
     77     if(dp[x][y].l)
     78         return dp[x][y];
     79 
     80     section rnt;
     81     rnt.l = 0x3f3f3f3f;
     82     rnt.r = 0;
     83     _for(i,0,4)
     84     {
     85         int nx = x+dx[i];
     86         int ny = y+dy[i];
     87         if(valid(nx,ny) && !vis[nx][ny] && a[x][y]>a[nx][ny])
     88         {
     89             vis[nx][ny] = true;
     90             section t = dfs(nx,ny);
     91             vis[nx][ny] = false;
     92             rnt.l = min(rnt.l,t.l);
     93             rnt.r = max(rnt.r,t.r);
     94         }
     95     }
     96     return dp[x][y] = rnt;
     97 }
     98 int main()
     99 {
    100 //    freopen("test.in","r+",stdin);
    101 
    102     N = read(),M = read();
    103     memset(a,0x3f,sizeof(a));
    104     memset(ok,0,sizeof(ok));
    105     _for(i,1,N+1)
    106     _for(j,1,M+1)
    107     {
    108         a[i][j] = read();
    109         if(i==N)
    110             dp[i][j].l = dp[i][j].r = j;
    111     }
    112 
    113     _for(i,1,M+1)
    114     {
    115         _rep(j,i-1,-1)
    116         if(a[N][j]>=a[N][j+1])
    117         {
    118             dp[N][i].l = j+1;
    119             break;
    120         }
    121         _for(j,i+1,M+2)
    122         if(a[N][j]>=a[N][j-1])
    123         {
    124             dp[N][i].r = j-1;
    125             break;
    126         }
    127     }
    128     bfs();
    129     _for(i,1,M+1)
    130     {
    131         if(!dp[1][i].l)
    132         {
    133             vis[1][i] = 1;
    134             dfs(1,i);
    135             vis[1][i] = 0;
    136         }
    137     }
    138 
    139     int cnt = 0;
    140     _for(i,1,M+1)
    141     if(!ok[i])
    142     {
    143         cnt ++;
    144     }
    145     if(cnt)
    146     {
    147         printf("0\n%d",cnt);
    148         return 0;
    149     }
    150 
    151     sort(dp[1],dp[1]+M+1);
    152 
    153     int now = 1,i = 1;
    154     while(i<M+1)
    155     {
    156         int mx = 0;
    157         while(i<M+1 && dp[1][i].l<=now)
    158         {
    159             mx = max(mx,dp[1][i].r);
    160             i ++;
    161         }
    162         if(dp[1][i].l==INT_MAX && now<M)
    163         {
    164             cnt ++;
    165             break;
    166         }
    167         if(mx<=now-1) break;
    168         now = mx+1;
    169         cnt ++;
    170     }
    171 
    172     printf("1\n%d",cnt);
    173     return 0;
    174 }

转载于:https://www.cnblogs.com/Asurudo/p/11392419.html