Redand black

BFS

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

int n, m, sx, sy;
const int N = 1e2+10;
char s[N][N];
int use[N][N];
int qwe[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};     //上下左右
bool jg(int x, int y)            //判断是否能走
{
  if (x<1 || x>n || y<1 || y>m)                 //超出边界
    return false;
  if (s[x][y] == '#')            //为#
    return false;
  if (use[x][y] == 1)            //走过了
    return false;
  return true;
}
void bfs()
{
  memset(use, 0, sizeof use);    //初始化
  queue<pair<int, int> > que;    //定义队列，对象有两个属性使用pair
  que.emplace(sx, sy);           //队列末尾插入新元素
  use[sx][sy] = 1;               //标记找到的位子
  int sum = 0;                   //能到达的瓷砖总数量
  while (!que.empty())           //当前位子的上下左右能否走
  {
    pair<int, int> u = que.front();             //返回首元素的两个属性
    que.pop();
    sum++;
    for (int i = 0; i < 4; i++)  //洪水填充
    {                            //扩散到周边
      int nx = u.first + qwe[i][0];             //访问u的第一个属性值
      int ny = u.second + qwe[i][1];            //访问u的第一个属性值
      if (jg(nx, ny))
      {
        use[nx][ny] = 1;         //能走的地砖标记上
        que.emplace(nx, ny);     //放入队列
      }
    }
  }
  printf("%d\n", sum);
}
int main()
{
  while ((scanf("%d %d", &m, &n), m + n) != 0)  //输入零程序结束
  {
    for (int i = 1; i <= n; i++)                //读地图
      scanf("%s", s[i] + 1);
    for (int i = 1; i <= n; i++)                //找当前位子
    {
      for (int j = 1; j <= m; j++)
      {
        if (s[i][j] == '@')                     //寻找起点并标记
        {
          sx = i;
          sy = j;
        }
      }
    }
    bfs();
  }
  return 0;
}

笔记：洪水填充就是类似油漆桶，它可以把一块被圈起来的区域全部染色，扫雷游戏也是用这种方式可以展开大片的空地

DFS

#include<cstdio>
#include<queue>
#include<string.h>
using namespace std;

const int N = 1e2 + 10;
int n, m, sx, sy;
int ans;
char s[N][N];
int use[N][N];
int qwe[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };    //上下左右
bool jg(int x, int y)                             //判断是否能走
{
  if (x<1 || x>n || y<1 || y>m)                   //超出边界
    return false;
  if (s[x][y] == '#')                             //为#
    return false;
  if (use[x][y])                                  //走过了
    return false;
  return true;
}
void dfs(int x, int y)
{
  if(jg(x,y))
  {
    use[x][y] = 1;                                 //标记找到的位子
    ans++;
    for (int i = 0; i < 4; i++)                    //洪水填充
    {
      int nx = x + qwe[i][0];
      int ny = y + qwe[i][1];
      dfs(nx, ny);
    }
  }
  else
    return;
}

int main()
{
  while (scanf("%d %d", &m, &n), m + n)
  {
    memset(use, 0, sizeof use);                    //初始化
    for (int i = 1; i <= n; i++)
      scanf("%s", s[i] + 1);
    int x, y;
    for (int i = 1; i <= n; i++)                   //找当前位子
    {
      for (int j = 1; j <= m; j++)
      {
        if (s[i][j] == '@')
        {
          x = i;
          y = j;
        }
      }
    }
    ans = 0;
    dfs(x, y);
    printf("%d\n", ans);
  }
  return 0;
}

笔记：bfs和dfs在正常情况下二者的时间复杂度都是相同的，但是根据题型，bfs的时间会更快一些

版权声明：

本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/qq_49006646/article/details/107319460