Submission #1222175

#TimeUsernameProblemLanguageResultExecution timeMemory
1222175firegirlwaterboyTracks in the Snow (BOI13_tracks)C++20
77.50 / 100
524 ms112140 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1}; void solve() { int n, m; cin >> n >> m; vector<string> grid(n); for (int i = 0; i < n; i++) { cin >> grid[i]; } deque<pii> q; q.push_front({0, 0}); vector<vector<int>> d(n, vector<int>(n)); d[0][0] = 1; int ans = 1; while (q.size()) { pii c = q.front(); q.pop_front(); int x = c.first, y = c.second; ans = max(ans, d[x][y]); for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m || grid[nx][ny] == '.') continue; if (d[nx][ny]) continue; if (grid[nx][ny] == grid[x][y]) { d[nx][ny] = d[x][y]; q.push_front({nx, ny}); } else { d[nx][ny] = d[x][y] + 1; q.push_back({nx, ny}); } } } cout << ans << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...