本文主要是介绍Codeforces Round #456 (Div. 2) D. Fishes（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/912/problem/D
题目是挺简单的。。。可是我怎么就没想到去bfs去搜呢？？？我大概是个zz吧
代码：
#include<bits/stdc++.h>
#define mp make_pair
#define xx first
#define yy second
using namespace std;
typedef long long ll;
int n,m,r,k;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
ll cal(int i,int j)
{ll x=min(n-r+1,i)-max(1,i-r+1)+1;ll y=min(m-r+1,j)-max(1,j-r+1)+1;ll ret=x*y;return ret;
}
struct node
{int x,y;ll tot;node(int _x,int _y,ll _tot):x(_x),y(_y),tot(_tot){}bool operator < (const node &o)const{return tot<o.tot;}
};
priority_queue<node> Q;
map<pair<int,int>,int> book;
bool check(int x,int y)
{if(x<1||x>n||y<1||y>m||book.find(mp(x,y))!=book.end())return true;return false;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);ll res=0;scanf("%d%d%d%d",&n,&m,&r,&k);book[mp(r,r)]=1;Q.push(node(r,r,cal(r,r)));while(k--){node now=Q.top();Q.pop();res+=now.tot;for(int i=0;i<4;i++){int tx=now.x+dir[i][0];int ty=now.y+dir[i][1];if(!check(tx,ty)){book[mp(tx,ty)]=1;Q.push(node(tx,ty,cal(tx,ty)));}}}printf("%.10lf\n",1.0*res/(1LL*(n-r+1)*(m-r+1)));return 0;
}这篇关于Codeforces Round #456 (Div. 2) D. Fishes（BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
