分析
审题:不是问前后留下的岛屿差,而是,消失的岛屿数。所以,尽管一个岛屿可能变成多个,但仅仅表示它没有消失。
首先,遇到一个‘#’用dfs访问,全部标记,计数原始岛屿数加一
其次,dfs中统计当前岛屿未被淹没的‘#’个数remain;最终remain大于0,未消失的岛屿数加一。
最后,输出原来的岛屿数-未消失的岛屿
- 该题保证‘#’一定被水包围,其实不用检查下一跳的坐标
- 也可以把判断是否邻水糅到dfs的循环里,看个人习惯
- 读取成行的字符,小心换行符
C++
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+5;
#define efor(i,s,e) for(int i=s;i<=e;i++)
#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl
int n;
int remain;//当前岛屿剩下多少#
string a[1010];
bool vis[1010][1010];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void init(){
cin>>n;
ffor(i,0,n){
cin>>a[i];
}
// ffor(i,0,n){
// ffor(j,0,n) out(a[i][j]);
// nl;
// }
}
bool check(int i,int j){
return i<n&&i>=0&&j<n&&j>=0;
}
bool nextSea(int x,int y){
ffor(i,0,4){
int nx=x+dx[i];
int ny=y+dy[i];
// out(nx);out(ny);out(a[nx][ny]);nl;
if(check(nx,ny)&&a[nx][ny]=='.') return true;
}
return false;
}
void dfs(int x,int y){
vis[x][y]=1;
if(!nextSea(x,y)) remain++;
ffor(i,0,4){
int nx=x+dx[i];
int ny=y+dy[i];
if(check(nx,ny)&&a[nx][ny]=='#'&&!vis[nx][ny]){
dfs(nx,ny);
}
}
}
void acWing(){
init();
int old=0,residue=0;//原来岛屿数,和未完全淹没的岛屿数
ffor(i,0,n) ffor(j,0,n){
if(a[i][j]=='#'&&!vis[i][j]){
old++;
remain=0;//当前岛屿剩余的#数量
dfs(i,j);
if(remain > 0) residue++;
}
}
cout<<old-residue<<endl;
}
int main()
{
// init();
// remain=0;
// dfs(1,1);
// out(remain);nl;
// out(nextSea(1,1));nl;
// out(nextSea(4,4));nl;
acWing();
return 0;
}
简化版
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+5;
#define efor(i,s,e) for(int i=s;i<=e;i++)
#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl
int n;
int remain;//当前岛屿剩下多少#
string a[1010];
bool vis[1010][1010];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void init(){
cin>>n;
ffor(i,0,n){
cin>>a[i];
}
}
void dfs(int x,int y){
vis[x][y]=1;
bool nxtWater=false;
ffor(i,0,4){
int nx=x+dx[i];
int ny=y+dy[i];
if(a[nx][ny]=='.') nxtWater=true;
if(a[nx][ny]=='#'&&!vis[nx][ny]){
dfs(nx,ny);
}
}
if(!nxtWater) remain++;
}
void acWing(){
init();
int old=0,residue=0;//原来岛屿数,和未完全淹没的岛屿数
ffor(i,0,n) ffor(j,0,n){
if(a[i][j]=='#'&&!vis[i][j]){
old++;
remain=0;//当前岛屿剩余的#数量
dfs(i,j);
if(remain > 0) residue++;
}
}
cout<<old-residue<<endl;
}
int main()
{
acWing();
return 0;
}