递推

#include <bits/stdc++.h>
using namespace std;
int n, m, mx, my;
char f[10005][105][105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> n >> my >> mx;
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            cin >> f[0][i][j];
    f[0][mx][my] = 'M';

    // 初始情况检查
    bool flag = true;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (f[0][i][j] == '.')
                flag = false;
    if (flag)
    {
        cout << 0 << "\n";
        return 0;
    }

    for (int day = 1;; day++)
    {
        bool flag = true; // 是否搞定了
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                if (f[day - 1][i][j] == '*')
                {
                    f[day][i][j] = '*';
                    continue;
                }
                if (f[day - 1][i - 1][j - 1] == 'M' ||
                    f[day - 1][i - 1][j] == 'M' ||
                    f[day - 1][i - 1][j + 1] == 'M' ||
                    f[day - 1][i][j - 1] == 'M' ||
                    f[day - 1][i][j] == 'M' ||
                    f[day - 1][i][j + 1] == 'M' ||
                    f[day - 1][i + 1][j - 1] == 'M' ||
                    f[day - 1][i + 1][j] == 'M' ||
                    f[day - 1][i + 1][j + 1] == 'M')
                {
                    f[day][i][j] = 'M';
                }
                else
                {
                    f[day][i][j] = '.';
                    flag = false;
                }
            }
        /*
        cout << day << "\n";
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
                cout << f[day][i][j];
            cout << "\n";
        }
        */
        if (flag)
        {
            cout << day << "\n";
            return 0;
        }
    }
    return 0;
}

广搜

#include <bits/stdc++.h>
using namespace std;
int n, m, mx, my;
char f[105][105];
int dis[105][105];
queue<pair<int, int>> q;
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> n >> my >> mx;
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= m; j++)
            cin >> f[i][j];
    f[mx][my] = 'M';
    q.push(make_pair(mx, my));
    dis[mx][my] = 0;
    while (!q.empty())
    {
        pair<int, int> now = q.front();
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            int nxtX = now.first + dx[i];
            int nxtY = now.second + dy[i];
            if (f[nxtX][nxtY] == '.')
            {
                q.push(make_pair(nxtX, nxtY));
                f[nxtX][nxtY] = 'M';
                dis[nxtX][nxtY] = dis[now.first][now.second] + 1;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans, dis[i][j]);
    cout << ans;
    return 0;
}