题解 - 帖子 - CQUPT OJ

首先阅读题目，想要最大化路径步数就得求出每一个点除了#起点的最大步数，所以对每个点进行bfs，最后出队列的必定是最远点，然后取max就可以了。

#include <bits/stdc++.h>

using namespace std;

int n, m;
int ans;

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

char mp1[30][30], mp2[30][30];
int mp[30][30];

void bfs(int x, int y) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            mp2[i][j] = mp1[i][j];
            mp[i][j] = 0;
        }

    if (mp2[x][y] == '#')
        return;

    queue<pair<int, int> > q;

    q.push({ x, y });

    mp2[x][y] = '#';

    while (q.size()) {
        auto t1 = q.front();
        q.pop();
        int x1 = t1.first, y1 = t1.second;

        for (int i = 0; i <= 3; i++) {
            int nx = x1 + dx[i], ny = y1 + dy[i];

            if (nx <= n && nx >= 1 && ny >= 1 && ny <= m && mp2[nx][ny] == '.') {
                mp2[nx][ny] = '#';
                mp[nx][ny] = mp[x1][y1] + 1;
                q.push({ nx, ny });
            }
        }
        if (q.empty())
            ans = max(ans, mp[x1][y1]);
    }
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j++) {
            mp1[i][j] = s[j - 1];
            mp2[i][j] = mp1[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            bfs(i, j);
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int _ = 1;
    // freopen("3.in","r",stdin);
    // freopen("3.out","w+",stdout);
    // cin>>_;
    while (_--) {
        solve();
    }

    return 0;
}