제출 #885675

#제출 시각아이디문제언어결과실행 시간메모리
885675mariam197Tracks in the Snow (BOI13_tracks)C++17
100 / 100
576 ms235236 KiB
#include<bits/stdc++.h> #pragma GCC optimize("Ofast") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> #define ll long long #define int long long #define f first #define s second #define ld long double #define mod 1000000007 #define all(x) x.begin() , x.end() #define rall(x) x.rbegin() , x.rend() using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>; double distance(int x1,int y1,int x2,int y2) { return abs(x1-x2)*abs(x1-x2)+abs(y1-y2)*abs(y1-y2); } int n,m; string snow[4003]; int vis[4003][4003]; bool valid(int i,int j){ if(i>=0 && j>=0 && i<n && j<m && snow[i][j]!='.' && vis[i][j]==0){ return 1; } return 0; } int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("nocross.in","r",stdin); //freopen("nocross.out","w",stdout); cin>>n>>m; for(int i=0;i<n;i++){ cin>>snow[i]; } deque<pair<int,int> > q; q.push_front({0,0}); vis[0][0]=1; int ans=1; while(!q.empty()){ int i=q.front().f,j=q.front().s; q.pop_front(); ans=max(ans,vis[i][j]); for(int k=0;k<4;k++){ int x=i+dx[k],y=j+dy[k]; if(valid(x,y)){ if(snow[x][y]==snow[i][j]){ vis[x][y]=vis[i][j]; q.push_front({x,y}); } else{ vis[x][y]=vis[i][j]+1; q.push_back({x,y}); } } } } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...