首先阅读题目,想要最大化路径步数就得求出每一个点除了#起点的最大步数,所以对每个点进行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;
}