Submission #1207834

#TimeUsernameProblemLanguageResultExecution timeMemory
1207834Madhav_1608Tracks in the Snow (BOI13_tracks)C++20
19.79 / 100
1195 ms221272 KiB
#include <iostream> #include <stack> #include <queue> #include <string> #include <algorithm> #include <vector> #include <map> #include <set> #include <climits> #include <cmath> #include <unordered_map> #include <unordered_set> #include <numeric> #include <iomanip> #include <cstring> #include <stdio.h> #include <assert.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<string> vs; typedef vector<long long> vll; typedef pair<ll,ll> pll; #define double long double #define F first #define S second const double eps = 1e-9; #define FOR(i,a,b) for(long long i=a;i<b;i++) #define all(v) v.begin(),v.end() template <typename I> void print(vector<I> &v){ FOR(i,0,v.size()){cout << v[i] << " ";} cout << "\n"; } ll gcd(ll a,ll b){ if(a==0){return b;} else if(b==0){return a;} else if(a<b){return gcd(b%a,a);} else{return gcd(a%b,b);} } ll lcm(ll a,ll b){ return (a/gcd(a,b))*b; } void setIO(string name = "") { freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output freopen((name + ".out").c_str(), "w", stdout); } void init_code(){ #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif } void solve(){ // store very big numbers may mean log2 ll h,w; cin >> h >> w; vector<string> grid(h); FOR(i,0,h) cin >> grid[i]; vector<vll> dist(h,vll(w,INT_MAX)); dist[0][0] = 1; deque<pll> d; vector<vector<bool>> visited(h,vector<bool>(w,false)); d.push_front({0,0}); while(!d.empty()){ pll curr = d.front(); d.pop_front(); if(visited[curr.F][curr.S]) continue; visited[curr.F][curr.S] = true; if(curr.F>0){ ll alt = dist[curr.F][curr.S]; ll wt = 0; if(grid[curr.F][curr.S]!=grid[curr.F-1][curr.S]) wt++; if((alt+wt)<dist[curr.F-1][curr.S]){ dist[curr.F-1][curr.S] = alt+wt; if(wt==0){ d.push_front({curr.F-1,curr.S}); } else{ d.push_back({curr.F-1,curr.S}); } } } if(curr.S>0){ ll alt = dist[curr.F][curr.S]; ll wt = 0; if(grid[curr.F][curr.S]!=grid[curr.F][curr.S-1]) wt++; if((alt+wt)<dist[curr.F][curr.S-1]){ dist[curr.F][curr.S-1] = alt+wt; if(wt==0){ d.push_front({curr.F,curr.S-1}); } else{ d.push_back({curr.F,curr.S-1}); } } } if(curr.F<(h-1)){ ll alt = dist[curr.F][curr.S]; ll wt = 0; if(grid[curr.F][curr.S]!=grid[curr.F+1][curr.S]) wt++; if((alt+wt)<dist[curr.F+1][curr.S]){ dist[curr.F+1][curr.S] = alt+wt; if(wt==0){ d.push_front({curr.F+1,curr.S}); } else{ d.push_back({curr.F+1,curr.S}); } } } if(curr.S<(w-1)){ ll alt = dist[curr.F][curr.S]; ll wt = 0; if(grid[curr.F][curr.S]!=grid[curr.F][curr.S+1]) wt++; if((alt+wt)<dist[curr.F][curr.S+1]){ dist[curr.F][curr.S+1] = alt+wt; if(wt==0){ d.push_front({curr.F,curr.S+1}); } else{ d.push_back({curr.F,curr.S+1}); } } } } ll ans = 0; FOR(i,0,h){ FOR(j,0,w){ if(grid[i][j]=='.') continue; ans = max(ans,dist[i][j]); } } cout << ans << "\n"; } signed main(){ //setIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // init_code(); ll t=1; // cin >> t; while(t--){ solve(); } return 0; }

Compilation message (stderr)

tracks.cpp: In function 'void setIO(std::string)':
tracks.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp: In function 'void init_code()':
tracks.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...