Submission #713260

#TimeUsernameProblemLanguageResultExecution timeMemory
713260cfjasonTracks in the Snow (BOI13_tracks)C++17
0 / 100
1016 ms147068 KiB
#include <bits/stdc++.h> #define INF 2147483647 using namespace std; vector<array<int, 2>> offsets = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} }; int main (int argc, char *argv[]) { int h, w; cin >> h >> w; vector<string> grid(h); for (int i = 0; i < h; i++) { cin >> grid[i]; } vector<vector<int>> distance(h, vector<int>(w, INF)); deque<array<int, 2>> toVisit; toVisit.push_front({0, 0}); distance[0][0] = 0; int result = 0; while (!toVisit.empty()) { auto tp = toVisit.front(); toVisit.pop_front(); for (auto offset : offsets) { int x = tp[0] + offset[0]; int y = tp[1] + offset[1]; if(x < 0 || x >=h || y < 0 || y >= w) continue; array<int, 2> pos = {x, y}; if(distance[tp[0]][tp[1]] + (grid[pos[0]][pos[1]] != grid[tp[0]][tp[1]]) < distance[pos[0]][pos[1]]){ distance[pos[0]][pos[1]] = distance[tp[0]][tp[1]] + (grid[pos[0]][pos[1]] != grid[tp[0]][tp[1]]) ; result = std::max(result, distance[pos[0]][pos[1]]); if((grid[pos[0]][pos[1]] != grid[tp[0]][tp[1]])){ toVisit.push_back(pos); } else { toVisit.push_front(pos); } } } } cout << result << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...