【DFS】Sheba’s Amoebas

题目链接:

#include <iostream>
#include <cstring>
using namespace std;
char mapp[120][120];
bool vis[120][120];
int n, m;
int ans;
int direct[8][2] = {
  {0,1},{1,1},{1,0},{1,-1},
  {0,-1},{-1,-1},{-1,0},{-1,1},
};
void init() 
{
  memset(mapp, 0, sizeof(mapp));
  memset(vis, false, sizeof(vis));
  ans = 0;
}
void dfs(int x,int y)
{
  int nowx;
  int nowy;
  for (int i = 0; i < 8; i++)
  {
    nowx = x + direct[i][0];
    nowy = y + direct[i][1];
    if (nowx >= 0 && nowx < n && nowy >= 0 && nowy < m && vis[nowx][nowy] == false && mapp[nowx][nowy] == '#')
    {
      vis[nowx][nowy] = true;
      mapp[nowx][nowy] = '.';
      dfs(nowx, nowy);
    }
  }
}
int main()
{
  while (cin >> n >> m)
  {
    init();
    for (int i = 0; i < n; i++)
      cin >> mapp[i];
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < m; j++)
      {
        if (mapp[i][j]=='#'&&vis[i][j]==false)
        {
          dfs(i, j);
          ans++;
        }
        
      }
    }
    cout << ans << endl;
  }
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

4 × 5 =