Submission #1000528

#TimeUsernameProblemLanguageResultExecution timeMemory
1000528HUYHDUVETracks in the Snow (BOI13_tracks)C++14
60.63 / 100
2091 ms44692 KiB
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; #define ff first #define sc second int const INF = 2e9; vector<int> di = {1, -1, 0, 0}, dj = {0, 0, 1, -1}; int n, m, min_d[4000][4000], ans = 1; string grid[4000]; int main(){ // freopen("A.IN", "r", stdin); // freopen("A.OUT", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(nullptr); int n, m; cin >> n >> m; for(int i = 0; i < n; i++) cin >> grid[i]; min_d[0][0] = 1; deque<pii> q; q.push_back({0,0}); while(!q.empty()){ pii cur = q.front(); q.pop_front(); ans = max(ans, min_d[cur.ff][cur.sc]); for(int i = 0; i < n; i++){ int ni = cur.ff + di[i]; int nj = cur.sc + dj[i]; if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue; if(min_d[ni][nj] != 0 || grid[ni][nj] == '.') continue; if(grid[cur.ff][cur.sc] == grid[ni][nj]){ min_d[ni][nj] = min_d[cur.ff][cur.sc]; q.push_front({ni, nj}); } else { min_d[ni][nj] = min_d[cur.ff][cur.sc] + 1; q.push_back({ni, nj}); } } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...