Submission #893148

#TimeUsernameProblemLanguageResultExecution timeMemory
893148vaneaTracks in the Snow (BOI13_tracks)C++14
97.81 / 100
896 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int label = 1, n, m; const int mxN = 4e3+10; const int mxN1 = 5e6+10; vector<int> adj[mxN1]; bool vis[mxN][mxN]; char matrix[mxN][mxN]; int idx[mxN][mxN], d[mxN1]; vector<int> xy = {1, 0, -1, 0}, yx = {0, 1, 0, -1}; void dfs(int i, int j) { char c = matrix[i][j]; idx[i][j] = label; vis[i][j] = true; for(int k = 0; k < 4; k++) { int a = i + xy[k], b = j + yx[k]; if(a < 0 || a >= n || b < 0 || b >= m) continue; if(matrix[a][b] == '.') continue; if(matrix[a][b] == c) { if(!vis[a][b]) dfs(a, b); } else { if(vis[a][b]) { adj[label].push_back(idx[a][b]); adj[idx[a][b]].push_back(label); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> matrix[i][j]; } } for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(matrix[i][j] != '.' && !vis[i][j]) { dfs(i, j); ++label; } } } queue<int> q; q.push(1); d[1] = 1; int ans = 0; while(!q.empty()) { auto node = q.front(); q.pop(); ans = max(ans, d[node]); for(auto it : adj[node]) { if(d[it] == 0) { d[it] = d[node]+1; q.push(it); } } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...