1 solutions

  • 0
    @ 2025-12-10 19:08:55
    #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