제출 #1000181

#제출 시각아이디문제언어결과실행 시간메모리
1000181a5a7Tracks in the Snow (BOI13_tracks)C++14
2.19 / 100
311 ms219732 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using indexedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; char grid[n][m]; ll dist[n][m]; int visited[n][m]; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ cin >> grid[i][j]; dist[i][j] = 1e18; visited[i][j] = 0; } } deque<pair<int, int>> q; dist[0][0] = 0; q.push_back({0, 0}); vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; while (!q.empty()){ auto x = q.front(); q.pop_back(); if (visited[x.first][x.second]) continue; visited[x.first][x.second] = 1; for (auto y : dir){ int nx = x.first + y.first; int ny = x.second + y.second; if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; if (grid[nx][ny] == '.') continue; int d = grid[nx][ny] == grid[x.first][x.second] ? 0 : 1; if (dist[nx][ny] > (d+dist[x.first][x.second])){ dist[nx][ny] = d+dist[x.first][x.second]; if (d == 0){ q.push_front({nx, ny}); }else{ q.push_back({nx, ny}); } } } } ll ans = 0; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (dist[i][j] == 1e18) continue; ans = max(ans, dist[i][j]); } } cout << (ans+1) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...