제출 #490097

#제출 시각아이디문제언어결과실행 시간메모리
490097keertanTracks in the Snow (BOI13_tracks)C++17
100 / 100
536 ms118784 KiB
/** * If you live in imaginary world when your imaginary situation encounter in * real situation you can't enjoiy it because you have to do pending work. * {This pending work appeared because you wasted that time for your useless * imagianry thinking .} */ #include<bits/stdc++.h> using namespace std; //#define int int64_t #define all(x) x.begin(),x.end() #define all1(x) x.rbegin(),x.rend() #define sz(x) (int)(x.size()) const int N=4e5+5,mod=1e9+7; vector<string> z(4000); int dis[4000][4000]; vector<int> dx{1,-1,0,0},dy{0,0,1,-1}; void solve(){ int n,m; cin>>n>>m; for (int i=0;i<n;i++){cin>>z[i];} int ans=1; deque<pair<int,int>> q; dis[0][0]=1; q.push_back({0,0}); while(!q.empty()){ pair<int,int> u=q.front(); q.pop_front(); ans=max(ans,dis[u.first][u.second]); for (int i=0;i<4;i++){ int x=u.first+dx[i],y=u.second+dy[i]; if (min(x,y)>=0 && x<n && y<m && z[x][y]!='.' && dis[x][y]==0){ if (z[u.first][u.second]==z[x][y]){ q.push_front({x,y}); dis[x][y]=dis[u.first][u.second]; } else{ q.push_back({x,y}); dis[x][y]=dis[u.first][u.second]+1; } } } } cout<<ans; } int32_t main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int tq=1; //cin>>tq; for (;tq;tq--){solve();} } //is a bruteforce possible? //think greedier, make more assumptions // if we you find solution using loop to decrease complexity use bs //stuck for more than 5 minutes? move on
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...