这道题怎么写啊
题目描述
【题目描述】
随着X年抗战的落幕，小日子过得很舒服的日本军队终被赶回了日本岛。虽然战争已经过去，但是依然存在许多的历史遗留问题。比如现在特工鱼大大面临的这个问题：他的一位同事在清理战场的时候因为敌人留下的地雷而壮烈牺牲。此事一出，举国震惊，鱼大大的上司要求鱼大大务必将此战场的所有地雷排扫干净，确保人民安全。现在鱼大大为了自身安全又把任务交给了你，他要求你务必将你负责的这块区域中的雷区清点干净,这样鱼大大知道了情况后排雷时的安全就有了大大的保障。
现在你做的是清点你负责的这片区域有多少块雷区，以及最大的雷区中有多少块地雷
注：地雷爆炸时会将四面八方紧邻的格子全部引爆，能互相引爆的地雷属于同一片雷区。
【输入格式】
第一行包含两个整数n，m
接下来的n行，每行输入m个字符来表示地图。2 ≤n,m ≤200
其中只有‘*’表示地雷，字符‘.’表示路径，字符‘#’表示杂物
【输出格式】
输出雷区的数量以及最大雷区中的地雷数量
【输入样例】
8 10
....**.#.#
.#.#......
..#...#.*#
.#.#.***..
#..***##.#
..#...#.#.
....*.....
.##*...##.
【输出样例】
3 7
我八连通的dfs不一样
void dfs(int x,int y){
a[x][y]='.';
for(int dx=-1;dx<=1;dx++){
for(int dy=-1;dy<=1;dy++){
int nx=x+dx,ny=y+dy;
if(0<=nx&&nx<n&&0<=ny&&ny<m&&a[nx][ny]=='W')
dfs(nx,ny);
}
}
}
1 个赞
我的55.00000000000001分的代码
总结
没骗你
#include<bits/stdc++.h>
using namespace std;
int n,m,res,cnt,maxx=INT_MIN;
char a[105][105];
void dfs(int x,int y){
a[x][y]='.';
cnt++;
for(int dx=-1;dx<=1;dx++){
for(int dy=-1;dy<=1;dy++){
int nx=x+dx,ny=y+dy;
if(0<=nx&&nx<n&&0<=ny&&ny<m&&a[nx][ny]=='*')
dfs(nx,ny);
}
}
}
int main() {
while(cin>>n>>m){
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(a[i][j]=='*'){
cnt=0;
dfs(i,j);
res++;
maxx=max(maxx,cnt);
}
}
}
cout<<res<<" "<<maxx<<'\n';
}
return 0;
}
