Submission #1120843

#TimeUsernameProblemLanguageResultExecution timeMemory
1120843vjudge1Tracks in the Snow (BOI13_tracks)C++17
100 / 100
839 ms224276 KiB
/* #ifndef ONLINE_JUDGE #include "AkbarKING.h" // aska geldi akbarking.h #else #define debug(...) #define debugArr(...) #define debugG(...) #endif */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/hash_policy.hpp> #define int long long #define $AzH_TxdmN$ ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr); #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") #pragma GCC optimize("Ofast") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("fast-math") #define ep emplace_back #define pb push_back #define pii pair<int,int> #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() using namespace std; using namespace __gnu_pbds; template <typename T> using __indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T> using __indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; const int sz = 4e3 +9; const int LOG = 63; const int MOD = 1e9+7; const int INF = 1e18; int dx[] = {-1,0,1,0}; int dy[] = {0,1,0,-1}; int dp[sz][sz]; bool used[sz][sz]; char a[sz][sz]; int n,m; bool inbound(const int &a, const int &b) { return 1 <= a && 1 <= b && a <= n && b <= m; } void djk() { dp[1][1] = 1; deque<pii>dq; dq.pb({1,1}); int x,y,gox,goy; while(!dq.empty()) { x = dq.front().first; y = dq.front().second; dq.pop_front(); for(size_t i = 0; i < 4; ++i) { gox = x + dx[i]; goy = y + dy[i]; if(inbound(gox,goy) && a[gox][goy] != '.' && dp[gox][goy] == 0) { if(a[gox][goy] == a[x][y]) { dp[gox][goy] = dp[x][y]; dq.push_front({gox,goy}); } else { dp[gox][goy] = dp[x][y] + 1; dq.pb({gox,goy}); } } } } } void solve() { cin>>n>>m; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { cin>>a[i][j]; } } djk(); int res = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { res = max(res,dp[i][j]); } } cout<<res<<'\n'; } signed main() { $AzH_TxdmN$ int t = 1; //cin>>t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...