Submission #445988

#TimeUsernameProblemLanguageResultExecution timeMemory
445988minhi1Tracks in the Snow (BOI13_tracks)C++14
100 / 100
803 ms131048 KiB
#include <bits/stdc++.h> #define forw(i,a,b) for (int i = (a); i <= (b); i++) #define ford(i,a,b) for (int i = (a); i >= (b); i--) #define rep(i,a,b) for (int i = (a); i < (b); i++) #define ff first #define ss second #define ALL(v) (v).begin(), (v).end() #define nl '\n' using namespace std; template<class X, class Y> bool minimize(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maximize(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } /* AHIHI */ #define MAX 4010 typedef long long ll; typedef pair<int, int> pii; const int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1}; int n,m,res,d[MAX][MAX]; char a[MAX][MAX]; bool ins(int u,int v) { return min(u,v) >= 1 && u <= n && v <= m; } void bfs() { deque<pii> q; q.push_back({1,1}); d[1][1] = 1; while (q.size()) { pii c = q.front(); q.pop_front(); maximize(res, d[c.ff][c.ss]); rep(i,0,4) { int u = c.ff + dx[i], v = c.ss + dy[i]; if (ins(u,v) && d[u][v] == 0 && a[u][v]!='.') { if (a[u][v] == a[c.ff][c.ss]) { d[u][v] = d[c.ff][c.ss]; q.push_front({u,v}); } else { d[u][v] = d[c.ff][c.ss] + 1; q.push_back({u,v}); } } } } } void solve(int tc) { cin >> n >> m; forw(i,1,n) forw(j,1,m) cin >> a[i][j]; bfs(); cout << res << nl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); // string name = "HT"; // freopen((name + ".inp").c_str(),"r",stdin); // freopen((name + ".out").c_str(),"w",stdout); int T = 1; // cin >> T; forw(i,1,T) solve(i); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...