Submission #713260

#	Time	Username	Problem	Language	Result	Execution time	Memory
713260		cfjason	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	1016 ms	147068 KiB

tracks

#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;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70