Submission #604200

#TimeUsernameProblemLanguageResultExecution timeMemory
604200jackkkkTracks in the Snow (BOI13_tracks)C++11
91.25 / 100
2112 ms1005760 KiB
// EMPTY // #include <stdio.h> #include <iostream> #include <string> #include <vector> #include <queue> #include <map> #include <array> #include <deque> #include <unordered_map> #include <unordered_set> #include <set> #include <algorithm> #include <stdlib.h> #include <math.h> #include <list> #include <float.h> #include <climits> using namespace std; void quit() { cout.flush(); exit(0); } char grid[4002][4002]; map<int, unordered_set<int>> adj; int id[4002][4002]; int curr_id = 1; deque <pair<int, int>> dq; vector<pair<int, int>> gto = {{1,0},{0,1},{-1,0},{0,-1}}; void flood(int a, int b){ id[a][b]=curr_id; char c = grid[a][b]; grid[a][b]='.'; dq.clear(); dq.emplace_back(a, b); while(!dq.empty()){ auto curr = dq.front(); dq.pop_front(); for(auto to : gto){ pair<int, int> nxt = {curr.first+to.first, curr.second+to.second}; if(grid[nxt.first][nxt.second] == c){ id[nxt.first][nxt.second]=curr_id; grid[nxt.first][nxt.second] = '.'; dq.push_back(nxt); } if(id[nxt.first][nxt.second]!=0 && id[nxt.first][nxt.second] != curr_id){ adj[id[nxt.first][nxt.second]].insert(curr_id); adj[curr_id].insert(id[nxt.first][nxt.second]); } } } curr_id++; } int main(void){ //freopen("qwer.in", "r", stdin); //freopen("qwer.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; for(int i = 0; i < 4002; i++){ for(int j = 0; j < 4002; j++){ grid[i][j]='.'; } } for(int i = 1; i <= n; i++){ string s; cin >> s; for(int j = 1; j <= m; j++){ grid[i][j]=s[j-1]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(grid[i][j] != '.'){ flood(i, j); } } } deque <int> dq; dq.push_back(1); vector <int> dist(curr_id, 1e9); dist[1]=0; while(!dq.empty()){ int curr = dq.front(); dq.pop_front(); for(int nxt : adj[curr]){ if(dist[curr]+1 < dist[nxt]){ dist[nxt]=dist[curr]+1; dq.push_back(nxt); } } } int ans = 0; for(int i = 1; i < curr_id; i++){ ans = max(ans, dist[i]); } cout << ans+1 << "\n"; quit(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...