bzoj 1619: [Usaco2008 Nov]Guarding the Farm 保卫牧场【bfs】
2024-09-30 19:16:40
不是严格小于是小于等于啊!!!!!不是严格小于是小于等于啊!!!!!不是严格小于是小于等于啊!!!!!
是我看不懂人话还是翻译不说人话= =
把所有格子按值排个序,bfs扩展打标记即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=705,dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
int n,m,a[N][N],ans,tot;
bool v[N][N];
struct qwe
{
int x,y,w;
qwe(int X=0,int Y=0,int W=0)
{
x=X,y=Y,w=W;
}
}p[N*N];
bool cmp(const qwe &a,const qwe &b)
{
return a.w>b.w;
}
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
inline bool ok(int x,int y,int pr)
{
return x>=1&&y>=1&&x<=n&&y<=m&&a[x][y]<=pr&&!v[x][y];
}
void bfs(qwe s)
{
ans++;
queue<qwe>q;
q.push(s);
v[s.x][s.y]=1;
while(!q.empty())
{
int x=q.front().x,y=q.front().y,w=q.front().w;
q.pop();
for(int i=0;i<8;i++)
if(ok(x+dx[i],y+dy[i],w))
v[x+dx[i]][y+dy[i]]=1,q.push(qwe(x+dx[i],y+dy[i],a[x+dx[i]][y+dy[i]]));
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
a[i][j]=read(),p[++tot]=qwe(i,j,a[i][j]);
sort(p+1,p+1+tot,cmp);
for(int i=1;i<=tot;i++)
if(!v[p[i].x][p[i].y])
bfs(p[i]);
printf("%d\n",ans);
return 0;
}
最新文章
- Android无需申请权限拨打电话
- 启动项目的时候报驱动错误: not support oracle driver 1.0
- POJ 3233 Matrix Power Series --二分求矩阵等比数列和
- mysql命令行操作
- shell script针对参数已经有配置好变量名称
- Asp.Net正则获取页面a标签里的内容
- 网络编程之PC版与Android手机版带断点续传的多线程下载
- 编码规范系列(一):Eclipse Code Templates设置
- [topcoder]TopographicalImage
- 前端工程之模块化(来自百度FEX)
- 快速排序(Quick Sort)
- linux chmod使用说明
- Unix命令操作
- linux_inode和block
- 什么是 lnmp 实现原理。
- 让微信,qq,uc浏览器使用全屏模式,全屏模式里,浏览器是不会上下左右滑动出现背景的
- Book : <;Hands-on ML with Sklearn &; TF>; pdf/epub
- String 常用函数
- JavaScript语法详解:if语句&;for循环&;函数
- Docker应用系列(五)| 构建Mongodb服务器
热门文章
- 【03】Html书写规范
- 关于Filter中ServletRequest和ServletResponse强转HttpServletRequest和HttpServletResponse
- HUST 1407(数据结构)
- 【状压+状态转移】A Famous Airport Managere
- [K/3Cloud] 树形单据体的应用说明
- 「CodePlus 2017 11 月赛」大吉大利,晚上吃鸡!
- Thinkphp5.0 的视图view的模板布局
- [bzoj2194]快速傅立叶之二_FFT
- laravel notification
- 总结react中遇到的坑和一些小的知识点