Submission #1043878

#TimeUsernameProblemLanguageResultExecution timeMemory
1043878davieduTracks in the Snow (BOI13_tracks)C++17
100 / 100
556 ms88908 KiB
#include <bits/stdc++.h> using namespace std; #define fastio ios_base::sync_with_stdio(0); cin.tie(0) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define ll long long struct P{ ll x, y; }; void dbg_out() { cerr << endl; } template <typename H, typename... T> void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); } #define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); } const int N = 4001; char grid[N][N]; int dist[N][N]; int h, w; int valid(int x, int y){ return (0 <= x && x < h) && (0 <= y && y < w); } int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; signed main(){ fastio; cin >> h >> w; for (int i=0; i<h; i++){ for (int j=0; j<w; j++){ cin >> grid[i][j]; } } memset(dist, -1, sizeof(dist)); int ans=1; queue<pair<int, int>> q0, q1; dist[0][0] = 1; q0.push({0, 0}); int x, y; int ctr=0; while (!q0.empty() || !q1.empty()){ while (!q0.empty()){ tie(x, y) = q0.front(); q0.pop(); ans = max(ans, dist[x][y]); for (int i=0; i<4; i++){ int a, b; a = dx[i]+x; b = dy[i]+y; if (!valid(a, b) || grid[a][b] == '.' || dist[a][b] != -1) continue; dist[a][b] = dist[x][y]; if (grid[a][b] != grid[x][y]){ dist[a][b]++; q1.push({a, b}); } else q0.push({a, b}); } } swap(q0, q1); } cout << ans << '\n'; }

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:46:9: warning: unused variable 'ctr' [-Wunused-variable]
   46 |     int ctr=0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...