[数据结构与算法]AcWing 1113. 红与黑

链接
https://www.acwing.com/problem/content/1115/

思路
广度优先搜索，深度优先搜索两个都ok

相关题目

643 动态网格 52.10% 简单
687 扫雷 63.76% 简单
1097 池塘计数 61.75% 简单
1106 山峰和山谷 53.79% 中等
1113 红与黑 58.13% 简单
1233 全球变暖 47.53% 简单
1402 星空之夜 49.52% 中等
1581 急性中风 44.54% 中等
3224 画图 33.17% 中等
4004 传送阵46.24% 中等

时间复杂度
O(m*n)

//BFS广度优先搜索
//#include <bits/stdc++.h> 万能头文件
#include <iostream>
#include <queue>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;//存放两维坐标
const int N = 25;

int n, m;
char g[N][N];

int bfs(int sx, int sy)
{
    queue<PII> q;
    q.push({sx, sy});
    g[sx][sy] = '#';
    int res = 0;//记录所有能搜到的点的数量
    
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    while (q.size())
    {
        auto t = q.front();//取出队头元素
        q.pop();//删去队头
        res ++ ;//从队列里每出来一个点，数量就 ++
        
        for (int i = 0; i < 4; i ++ )//扩展四个方向
        {
            int x = t.x + dx [i], y =t.y +dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != '.') continue;//当前位置走过，出界就continue
            g[x][y] = '#';//当前位置没有走过，标记一下
            q.push({x, y});//存到当前队列里
        }
    }
    return res;
}

int main()
{
    while (cin >> m >> n, n || m)
    {
        for (int i = 0; i < n; i ++ ) cin >>g[i];
        int x, y;
        for (int i = 0; i < n; i ++ )
            for ( int j = 0; j < m; j ++ )
                if (g[i][j] == '@')//设x,y为起始位置
                {
                    x = i;
                    y = j;
                }
        cout << bfs(x, y) <<endl;
    }
    
    return 0;
}