bzoj3137 [Baltic2013]tracks 题解

Describe

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

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

Solution

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

Code

#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==1||j==1||i==n||j==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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇