제출 #1043877

#제출 시각아이디문제언어결과실행 시간메모리
1043877davieduTracks in the Snow (BOI13_tracks)C++17
31.77 / 100
386 ms94516 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)); queue<pair<int, int>> q; int ans=1; dist[0][0] = 1; q.push({0, 0}); while (!q.empty()){ int x, y; tie(x, y) = q.front(); q.pop(); 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] == '.') continue; int v = dist[x][y] + (grid[a][b] != grid[x][y]); if (dist[a][b] == -1) { dist[a][b] = v; q.push({a, b}); } else dist[a][b] = min(dist[a][b], v); } } for (int i=0; i<h; i++){ for (int j=0; j<w; j++){ ans = max(ans, dist[i][j]); } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...