bzoj3137 [Baltic2013]tracks 题解

(Updated: )
oi

Describe

给定一片长方形的草地，有2种动物：兔子和狐狸。兔子走过草地会留下R，狐狸走过草地会留下F。每只动物从左上角进入草地，从右下角走出草地。其间，它可以上下左右乱跳（可以重复），经过的格子会被覆盖上它的脚印。每次草地上最多只有一只动物。

给你地图，问最少有多少只动物走过了草地。

Solution

先将每一个边缘点加入$queue$，再每一次$bfs$选高度最小的点拓展，取最大，计算出每个点最高可达到的水量，最后一减即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
inline int read(){int res=0,f=1;char ch=getchar();while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();return res*f;}
inline void write(int x){if(x<0) putchar('-'),x=-x;if(x<10) putchar(x+'0');else write(x/10),putchar(x%10+'0');}
int n,m,a[110][110],b[110][110],vis[110][110],ans;
struct node{int x,y,h;bool operator<(const node &t)const{return h>t.h;}};
priority_queue<node> q;
const int dx[]={0,0,1,-1},
          dy[]={1,-1,0,0};
inline void spfa(){
    while(!q.empty()){
        node u=q.top();q.pop();
        int x=u.x,y=u.y,h=u.h;
        for(int i=0;i<4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
                if(vis[xx][yy]) continue ;
                a[xx][yy]=max(a[xx][yy],h);
                vis[xx][yy]=1,q.push((node){xx,yy,a[xx][yy]});
            }
        }
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) b[i][j]=a[i][j]=read();
    while(!q.empty()) q.pop();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(i==1j==1i==nj==m) q.push((node){i,j,a[i][j]}),vis[i][j]=1;
    spfa();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ans+=a[i][j]-b[i][j];
    return write(ans),putchar('\n'),0;
}