Submission #1256639

#TimeUsernameProblemLanguageResultExecution timeMemory
1256639keremTracks in the Snow (BOI13_tracks)C++20
84.69 / 100
2102 ms190716 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fr first #define sc second #define pb push_back #define all(x) x.begin(),x.end() #define sp << " " << #define inf 1e15 #define N 1000 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef tuple<int,int,int> tiii; typedef pair<int,int> pii; void solve(){ int n,m; cin >> n >> m; char a[n][m]; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> a[i][j]; priority_queue<tiii,vector<tiii>,greater<tiii>> pq; pq.push({1,0,0}); int d[n][m],ans=0; memset(d,-1,sizeof(d)); while(!pq.empty()){ int x,y,val; tie(val,x,y)=pq.top(); pq.pop(); if(d[x][y]!=-1) continue; d[x][y]=val; ans=max(ans,val); if(x!=n-1 && a[x+1][y]!='.' && d[x+1][y]==-1) pq.push({val+(a[x+1][y]!=a[x][y]),x+1,y}); if(x!=0 && a[x-1][y]!='.' && d[x-1][y]==-1) pq.push({val+(a[x-1][y]!=a[x][y]),x-1,y}); if(y!=m-1 && a[x][y+1]!='.' && d[x][y+1]==-1) pq.push({val+(a[x][y+1]!=a[x][y]),x,y+1}); if(y!=0 && a[x][y-1]!='.' && d[x][y-1]==-1) pq.push({val+(a[x][y-1]!=a[x][y]),x,y-1}); } cout << ans << endl; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int test=1; //~ cin >> test; while(test--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...