八连通积水(简单DFS)

发布于 / Algorithm / 0 条评论

问题描述

求八连通块。

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

如图:
ans 为3

思路

遍历map数组,碰到W开始dfs,访问过的标记掉或者直接替换。

剪枝:循环时访问过的元素在主函数中的循环可不考虑,这一点题解中的“替换”思想很好的诠释了这一点。

题解

#include <iostream>
using namespace std;
char kk[101][101];
int N,M;
void dfs(int i,int j){
  kk[i][j]='*';
  int nx,ny;
  for(int o=-1;o<=1;o++)
    for(int p=-1;p<=1;p++){
      nx=i+o;ny=j+p;
      if(nx>=0&&nx<=N&&ny>=0&&ny<=M&&kk[nx][ny]=='W')  dfs(nx,ny);
    }
    return ;
}
int main(int argc, char *argv[]) {
    freopen("in.txt", "r", stdin);
  cin>>N>>M;
  for(int i=0;i<N;i++)
    for(int j=0;j<M;j++){
      cin>>kk[i][j];
    }
  int res=0;
  for(int i=0;i<N;i++)
    for(int j=0;j<M;j++){
      if(kk[i][j]=='W'){
        dfs(i,j);
        res++;
      }
    }
  cout<<res;
  return 0;	
}

 

转载原创文章请注明,转载自: 静沐暖阳 » 八连通积水(简单DFS)
Not Comment Found