제출 #710517

#제출 시각아이디문제언어결과실행 시간메모리
710517hafoTracks in the Snow (BOI13_tracks)C++14
0 / 100
839 ms138968 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 4e3 + 7; const ll oo = 1e17 + 69; int n, m, f[maxn][maxn]; char a[maxn][maxn]; pa d[] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; void bfs() { deque<pa> q; memset(f, -1, sizeof f); f[0][0] = 0; q.push_front({0, 0}); int ans = 0; while(!q.empty()) { int u = q.front().fi; int v = q.front().se; q.pop_front(); maxi(ans, f[u][v]); for(int k = 0; k < 4; k++) { int x = u + d[k].fi; int y = v + d[k].se; if(x < 0 || x == n || y < 0 || y == m || f[x][y] != -1) continue; int w = (a[u][v] != a[x][y]); f[x][y] = f[u][v] + w; if(w) q.pb({x, y}); else q.push_front({x, y}); } } cout<<ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>m; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin>>a[i][j]; bfs(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...