Submission #811976

#TimeUsernameProblemLanguageResultExecution timeMemory
811976devariaotaTracks in the Snow (BOI13_tracks)C++17
50.52 / 100
907 ms51912 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define ull unsigned long long #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second const int N = 4e3 + 5; const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; queue<pair<int, int>> q1, q2; char a[N][N]; bool vis[N][N]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int h, w, cnt = 0, ans = 0; cin >> h >> w; for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { cin >> a[i][j]; if (a[i][j] != '.') cnt++; } } q1.push({1, 1}); vis[1][1] = 1, cnt--; while (cnt > 0) { ans++; while (!q1.empty()) { int x = q1.front().fi, y = q1.front().se; q1.pop(); cnt--; for (int i = 0; i < 4; i++) { int tx = x + dx[i], ty = y + dy[i]; if (tx < 1 or ty < 1 or tx > h or ty > w or vis[tx][ty] or a[tx][ty] == '.') continue; else if (a[x][y] == a[tx][ty]) vis[tx][ty] = 1, q1.push({tx, ty}); else vis[tx][ty] = 1, q2.push({tx, ty}); } } q1 = q2; while (!q2.empty()) q2.pop(); } cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...