제출 #1120737

#제출 시각아이디문제언어결과실행 시간메모리
1120737MamedovTracks in the Snow (BOI13_tracks)C++17
100 / 100
607 ms112332 KiB
#pragma GCC optimize ("O3") #include <bits/stdc++.h> //#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp> #define pii pair<int, int> #define piii pair<pii, int> #define vi vector<int> #define vll vector<ll> #define vvi vector<vi> #define vpii vector<pii> #define vvpii vector<vpii> #define f first #define s second #define oo 1000000001 #define eb emplace_back #define pb push_back #define mpr make_pair #define size(v) (int)v.size() #define ln '\n' #define ull unsigned long long #define ll long long #define all(v) v.begin(), v.end() #define iospeed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) //#define pbase 361549 //#define imod 1073737591 //#define uimod 2147479307u //#define llmod 292187309552789533ll using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //using namespace __gnu_pbds; //template <typename T> //using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T> void show(vector<T> &v) { for (T i : v) { cout << i << ' '; } cout << ln; } int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; void solve() { int h, w; cin >> h >> w; vector<string>s(h); for (string &r : s) { cin >> r; } deque<array<int, 2>>q; vvi dist(h, vi(w, 0)); q.push_back({0, 0}); dist[0][0] = 1; int res = 1; while (!q.empty()) { auto [x, y] = q.front(); res = max(res, dist[x][y]); q.pop_front(); for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 0 && nx < h && ny >= 0 && ny < w && !dist[nx][ny] && s[nx][ny] != '.') { dist[nx][ny] = dist[x][y]; if (s[nx][ny] == s[x][y]) { q.push_front({nx, ny}); } else { ++dist[nx][ny]; q.push_back({nx, ny}); } } } } cout << res << ln; } int main() { iospeed; solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...