【[Offer收割]编程练习赛11 C】岛屿3
2024-08-31 03:56:52
【题目链接】:http://hihocoder.com/problemset/problem/1487
【题意】
中文题
【题解】
岛屿的数目对应了这个图中联通块的数目;
面积则对应有多少个方块;
周长。。。周长就是周长
每次新增加一个方块的时候;
对于联通块;
把每个坐标转换成一维的数字;
然后写个并查集;
对于周长;
查看这个格子周围4个格子;
如果有格子和它相邻;
则那一面不会算在周长里面;
则减掉;
如果没有格子相邻则加上一个单位的周长
【Number Of WA】
0
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 1100;
const int ZDD = 1000999;
int n,bb[ZDD];
bool bo[N][N];
LL ltk,mj,zc;
int zh(int x,int y)
{
return (x-1)*1000+y;
}
int zbb(int x)
{
if (bb[x]==x)
return x;
else
return bb[x] = zbb(bb[x]);
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf就别用了!
rep1(i,1,1000000) bb[i] = i;
cin >> n;
rep1(i,1,n)
{
int x,y;
cin >> x >> y;
x++,y++;
if (bo[x][y])
{
cout << ltk <<' '<<mj<<' '<<zc<<endl;
continue;
}
bo[x][y] = true,ltk++,mj++;
rep1(j,1,4)
{
int x1 = x+dx[j],y1 = y+dy[j];
if (bo[x1][y1])
{
zc--;
int yy = zh(x1,y1),xx = zh(x,y);
int r1 = zbb(yy),r2 = zbb(xx);
if (r1!=r2)
{
bb[r1] = r2;
ltk--;
}
}
else
zc++;
}
cout << ltk << ' ' << mj << ' ' << zc << endl;
}
return 0;
}
最新文章
- 基于 SailingEase WinForm Framework 开发优秀的客户端应用程序(目录)
- 闪电动画模拟(Dielectric Breakdown Model)附源码
- jquery 之ajax获取数据
- hdu1873优先队列
- UVa1607 poj1435 UVaLive1686 Gates
- [Regionals 2012 :: Asia - Tokyo ]
- C# 自动提交到百度ping服务
- 网页设计——3.html运行原理,基本标签
- SparkHiveContext和直接Spark读取hdfs上文件然后再分析效果区别
- Java基础学习(二)
- 贪心 C - Polycarp&#39;s New Job
- office excel Query 功能
- js,jsp里将数据库Date类型获取出来后格式化显示于界面
- mybatis传递Map和List集合示例
- Linux下用文件IO的方式操作GPIO(/sys/class/gpio)(转)
- $_SERVER[&#39;SCRIPT_FILENAME&#39;] 与 __FILE__ 区别
- activeMQ入门+spring boot整合activeMQ
- JSP传递数组给JS的方法
- 复现VGG19训练自定义图像分类
- Echarts的赋值,设置数据
热门文章
- 使用poi读取word2007(.docx)中的复杂表格
- bzoj 4318 OSU! —— 期望DP
- Coursera Algorithms week1 查并集 练习测验:3 Successor with delete
- Python 37 进程池与线程池 、 协程
- NYOJ999 师傅又被妖怪抓走了
- windows phone控件
- Java中last_insert_id的使用
- JS排序之快速排序
- AI.框架理论.语义网.语言间距.孤单
- Sobel算子取代:基于特定点方向的canny边缘检测