This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |