Submission #938029

#TimeUsernameProblemLanguageResultExecution timeMemory
938029TAhmed33Tracks in the Snow (BOI13_tracks)C++98
97.81 / 100
1766 ms1048576 KiB
            #include <bits/stdc++.h>
            using namespace std;
            int dx[4] = {0, -1, 0, 1};
            int dy[4] = {1, 0, -1, 0};
            int comp[4001][4001] = {};
            char arr[4001][4001]; 
            int n, m;
            bool check (int i, int j) {
            	return (i >= 1 && i <= n && j >= 1 && j <= m && arr[i][j] != '.');
            }
            void dfs (int i, int j) {
            	for (int l = 0; l < 4; l++) {
            		if (check(i + dx[l], j + dy[l]) && comp[i + dx[l]][j + dy[l]] == 0 && arr[i + dx[l]][j + dy[l]] == arr[i][j]) {
            			comp[i + dx[l]][j + dy[l]] = comp[i][j];
            			dfs(i + dx[l], j + dy[l]);
            		}
            	}
            }
            vector <int> adj[16000001];
            bool vis[16000001];
            signed main () {
            	memset(vis, false, sizeof(vis));
            	cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> arr[i][j];
            	int c = 0;
            	for (int i = 1; i <= n; i++) {
            		for (int j = 1; j <= m; j++) {
            			if (comp[i][j] == 0 && arr[i][j] != '.') {
            				c++;
            				comp[i][j] = c;
            				dfs(i, j);
            			}
            		}
            	}
            	for (int i = 1; i <= n; i++) {
            		for (int j = 1; j <= m; j++) {
            			if (arr[i][j] == '.') continue;
            			for (int l = 0; l < 4; l++) {
            				if (check(i + dx[l], j + dy[l])) {
            					if (comp[i + dx[l]][j + dy[l]] != comp[i][j]) {
            						adj[comp[i][j]].push_back(comp[i + dx[l]][j + dy[l]]);
            						adj[comp[i + dx[l]][j + dy[l]]].push_back(comp[i][j]);
            					}
            				}
            			}
            		}
            	}
             
            	queue <int> cur;
            	cur.push(comp[1][1]); vis[comp[1][1]] = 1;
            	int cnt = 1;
            	int ans = 0;
            	while (!cur.empty()) {
            		auto u = cur.size(); while (u--) {
            			int k = cur.front(); cur.pop(); 
            			ans = cnt;
            			for (auto j : adj[k]) if (!vis[j]) {
                          vis[j] = 1; cur.push(j);
                        }
            		}
            		cnt++;
            	}
            	cout << ans << '\n';
            }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...