bzoj3137 [Baltic2013]tracks 题解
Describe
给定一片长方形的草地，有2种动物：兔子和狐狸。兔子走过草地会留下R，狐狸走过草地会留下F。每只动物从左上角进入草地，从右下角走出草地。其间，它可以上下左右乱跳（可以重复），经过的格子会被覆盖上它的脚印。每次草地上最多只有一只动物。
给你地图，问最少有多少只动物走过了草地。
Solution
先将每一个边缘点加入queue，再每一次bfs选高度最小的点拓展，取最大，计算出每个点最高可达到的水量，最后一减即可。
Code
代码语言：javascript复制#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 '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;
}
