题解——面积(area.cpp)
2024-10-06 13:17:42
题目来源&题面简述：
思路与算法选择：
只有*里面的部分对我们有用，所以可以将 *号外的部分标记一下。
可以用著名的BFS大法实现此过程。（连通块）
连通块模板：
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x;
int y;
node(){}
node(int x1,int y1):x(x1),y(y1){}
};
int n,m;
int u[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int head=1;
int tail=1;
int s[105][105];
int sum=0;
void bfs(int x,int y)
{
queue<node>Q;
s[x][y]=0;
Q.push(node(x,y));
while(!Q.empty()){
node a=Q.front();
Q.pop();
for(int i=0;i<4;i++){
int xx=u[i][0]+a.x;
int yy=u[i][1]+a.y;
if(xx>=0&&xx<n&&yy>=0&&yy<m&&(s[xx][yy])){
s[xx][yy]=0;
Q.push(node(xx,yy));
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>s[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[i][j]){
sum++;
bfs(i,j);
}
}
}
cout<<sum<<endl;
return 0;
}
这里只需按模板改就行了。
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x;
int y;
node(){}
node(int x1,int y1):x(x1),y(y1){}
};
int n,m;
int u[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int head=1;
int tail=1;
int s[105][105];
int sum=0;
void bfs(int x,int y)
{
queue<node>Q;
s[x][y]=-1;
Q.push(node(x,y));
while(!Q.empty()){
node a=Q.front();
Q.pop();
for(int i=0;i<4;i++){
int xx=u[i][0]+a.x;
int yy=u[i][1]+a.y;
if(xx>=0&&xx<n&&yy>=0&&yy<m&&(s[xx][yy]==0)){
s[xx][yy]=-1;
Q.push(node(xx,yy));
}
}
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>s[i][j];
}
}
for(int i=0;i<m;i++){
bfs(0,i);
}
for(int j = 0;j<n;++j) {
bfs(j,0);
}
for(int i=0;i<m;i++){
bfs(n-1,i);
}
for(int j = 0;j<n;++j) {
bfs(j,m-1);
}
int ans = 0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(s[i][j]==0) {
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
最新文章
- OSGi 基本原理
- ttf,eot,woff,svg,字体格式介绍及使用方法
- postgres 正则表达式 转
- Try out the latest C++ compiler toolset without waiting for the next update of Visual Studio
- fiddler filter 过滤css 图片等
- GCD 深入理解（一）
- oc学习之路----application.keyWindow.rootViewController与self.window.rootViewController与[self.window makeKeyAndVisible];小发现
- linux 备份日志文件
- 如何使用sublime编辑器运行python程序
- Linux设置自启动
- Linux centos7环境下安装JDK的步骤详解
- L1、L2范数理解
- spring-boot的三种启动方式[z]
- Dbvisualizer软件设置SQL语句的自动提示功能
- 跨域资源共享（CORS）--跨域ajax
- 杨恒说李的算法好-我问你听谁说的-龙哥说的（java中常见的List就2个）（list放入的是原子元素）
- thinkphp 查询单个“年-月-日” FROM_UNIXTIME
- Gitlab+Jenkins学习之路（六）之Jenkins部署、升级和备份
- C语言以字符形式读写文件
- 安装pip最简单的方法