1 solutions
-
0
#include<bits/stdc++.h> using namespace std; # define int long long int n, ca, sz[200005]; int h, w, hw[21][21]; int len = 0; map<pair<pair<int, int>, pair<int, int>>, int>mpp; signed main() { cin >> h >> w; string s; for (int i = 1; i <= h; i++) { cin >> s; for (int j = 0; j < w; j++) { if (s[j] == '.')hw[i][j + 1] = 1; else hw[i][j + 1] = -1; } } vector<pair<int, int>>stt, edd; for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { if (hw[i][j] == 1) { stt.push_back({i, j}); edd.push_back({i, j}); } } } // cout<<stt.size()<<edd.size(); int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0}; for (int i = 0; i < stt.size(); i++) { int dis[21][21], vis[21][21]; memset(dis, 0, sizeof(dis)); memset(vis, 0, sizeof(vis)); queue<pair<pair<int, int>, int>>q; q.push({{stt[i].first, stt[i].second}, 0}); vis[stt[i].first][stt[i].second] = 1; while (!q.empty()) { auto k = q.front(); q.pop(); // cout<<k.first.first<<" "<<k.first.second<<" "<<k.second<<endl; for (int i = 0; i <= 3; i++) { int px = k.first.first + dx[i]; int py = k.first.second + dy[i]; if (px >= 1 && px <= h && py >= 1 && py <= w && !vis[px][py]) { if (hw[px][py] == 1) { dis[px][py] = max( dis[px][py], k.second + 1); vis[px][py] = 1; q.push({{px, py}, k.second + 1}); len = max(len, dis[px][py]); } } } } } cout << len; }
- 1
Information
- ID
- 580
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 8
- Tags
- # Submissions
- 53
- Accepted
- 10
- Uploaded By