제출 #716377

#제출 시각아이디문제언어결과실행 시간메모리
716377S2speedTracks in the Snow (BOI13_tracks)C++17
71.56 / 100
1394 ms1048576 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize ("Ofast") #define all(x) x.begin() , x.end() #define sze(x) (ll)(x.size()) #define mp(x , y) make_pair(x , y) #define wall cout<<"--------------------------------------\n"; typedef long long int ll; typedef pair<ll , ll> pll; typedef pair<int , int> pii; typedef double db; typedef pair<pll , ll> plll; typedef pair<int , pii> piii; typedef pair<pll , pll> pllll; const ll maxn = 4e3 + 17 , maxv = 16e6 + 17 , md = 1e9 + 7 , inf = 2e16; vector<int> adj[maxv][2] , f , g; char a[maxn][maxn]; bool mark[maxv]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n , m; cin>>n>>m; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ cin>>a[i][j]; } } for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < m ; j++){ int v = i * m + j; if(i > 0){ if(a[i - 1][j] != '.'){ adj[v][a[i - 1][j] != a[0][0]].push_back(v - m); } } if(j > 0){ if(a[i][j - 1] != '.'){ adj[v][a[i][j - 1] != a[0][0]].push_back(v - 1); } } if(i < n - 1){ if(a[i + 1][j] != '.'){ adj[v][a[i + 1][j] != a[0][0]].push_back(v + m); } } if(j < m - 1){ if(a[i][j + 1] != '.'){ adj[v][a[i][j + 1] != a[0][0]].push_back(v + 1); } } } } int lm = n * m - 1; mark[0] = mark[lm] = true; f.push_back(0); f.push_back(lm); g.push_back(0); g.push_back(lm); int ans; for(int j = 0 ; ; j++){ if(f.empty()){ ans = j - 1; break; } int x = 0; while(x < sze(f)){ int v = f[x++]; for(auto i : adj[v][j & 1]){ if(mark[i]) continue; mark[i] = true; f.push_back(i); g.push_back(i); } } f = g; g.clear(); } cout<<ans<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...