Submission #134498

#TimeUsernameProblemLanguageResultExecution timeMemory
134498wzyTracks in the Snow (BOI13_tracks)C++11
100 / 100
863 ms118916 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int,int> #define F first #define S second #define pb push_back #define mp mka string s[4005]; int dist[4005][4005]; deque<pair<int, int> > dq; int h , w; int dx[4] = { 0 , 1 , 0 , -1}; int dy[4] = {1 , 0 , -1 , 0}; int32_t main(){ ios::sync_with_stdio(false); cin.tie(0) , cout.tie(0); cin>>h>>w; for(int i = 0 ; i < h ; i ++){ cin>>s[i]; for(int j = 0 ; j < w ; j ++){ dist[i][j] = numeric_limits<int>::max() ; dist[i][j]--; } } dq.push_back(pair<int,int>(0,0)); int ans = 0; dist[0][0] = 0; while(!dq.empty()){ pii u = dq.front(); ans = max(ans , dist[u.first][u.second]+1); dq.pop_front(); for(int i = 0 ; i < 4 ; i++){ int x = u.first + dx[i] , y = u.second + dy[i]; if(x >= 0 && y >= 0 && x < h && y < w){ if(s[x][y] != s[u.first][u.second] && s[x][y] != '.' && dist[x][y] > (dist[u.first][u.second] + 1)){ dist[x][y] = dist[u.first][u.second] + 1; dq.push_back(pair<int,int>(x,y)); } else{ if(s[x][y] == s[u.first][u.second] && dist[x][y] > (dist[u.first][u.second])){ dist[x][y] = dist[u.first][u.second]; dq.push_front(pair<int,int>(x,y)); } } } } } cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...