传感器
2025-01-22 10:44:09
发布于：上海
14阅读
0回复
0点赞
传感器 DFS搜素
#include<bits/stdc++.h>
using namespace std;
char g[1010][1010];
int dir[8][2] = {{1,0},{-1,0},{1,1},{-1,-1},{0,1},{0,-1},{1,-1},{-1,1}};
int n,m;
void dfs(int x,int y){
g[x][y] = '.';
for(int i=0;i<8;i++){
int nx = x+dir[i][0];
int ny = y+dir[i][1];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && g[nx][ny]=='#'){
dfs(nx,ny);
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
}
}
int cnt = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]=='#'){
dfs(i,j);
cnt++;
}
}
}
cout<<cnt;
return 0;
}
传感器 BFS搜素
#include<bits/stdc++.h>
using namespace std;
char g[1010][1010];
int dir[8][2] = {{1,0},{-1,0},{1,1},{-1,-1},{0,1},{0,-1},{1,-1},{-1,1}};
int n,m;
struct node{
int x,y;
};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>g[i][j];
}
}
int cnt = 0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(g[i][j]=='#'){
cnt++;
//BFS
queue<node> q;
g[i][j] = '.';
q.push({i,j});
while(q.size()){
node u = q.front();
q.pop();
for(int i=0;i<8;i++){
int nx = u.x+dir[i][0];
int ny = u.y+dir[i][1];
if(nx>=1 && nx<=n && ny>=1 && ny<=m && g[nx][ny]=='#'){
q.push({nx,ny});
g[nx][ny] = '.';
}
}
}
}
}
}
cout<<cnt;
return 0;
}
这里空空如也
有帮助，赞一个