Submission #947736

#	Time	Username	Problem	Language	Result	Execution time	Memory
947736		blahbaka	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	490 ms	222184 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

int main() {
#define int long long
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, w;
  cin >> h >> w;

  /*
    *We can use the following greedy strategy to find our answer:

    Consider the graph with an edge between each pair of adjacent cells with
    tracks, where the weight is 0 if the tracks are the same and 1 otherwise.
    The answer is simply the longest shortest-path from the top left cell. This
    is because going from one track to another same one is like not leaving a
    node (hence the cost is $0$), while going from one track to a different one
    is like traversing the edge between two nodes (hence the cost is $1$). Since
    the weight of each edge is either 0 or 1 and we want the shortest paths from
    the top left cell to each other cell, we can apply 0/1 BFS. The time
    complexity of this solution is $\mathcal O(NM)$.
    */
  //
  int dy[] = {-1, 1, 0, 0};
  int dx[] = {0, 0, -1, 1};

  vector<string> grid(h);

  for (int i = 0; i < h; i++) {
    std::cin >> grid[i];
  }

  vector<vector<int>> lengths(h, vector<int>(w, LONG_LONG_MAX));
  auto works = [&](int x, int y) {
    return y >= 0 && y < h && x >= 0 && x < w && grid[y][x] != '.';
  };

  deque<pair<int, int>> bfs;
  bfs.push_back({0, 0});
  lengths[0][0] = 1;
  while (!bfs.empty()) {
    auto front = bfs.front();
    bfs.pop_front();
    for (int k = 0; k < 4; k++) {
      int x = front.first + dx[k];
      int y = front.second + dy[k];
      if (works(x, y) && lengths[y][x] == LONG_LONG_MAX) {
        if (grid[y][x] == grid[front.second][front.first]) {
          lengths[y][x] = lengths[front.second][front.first];
          bfs.push_front({x, y});
        } else {
          lengths[y][x] = lengths[front.second][front.first] + 1;
          bfs.push_back({x, y});
        }
      }
    }
  }
  int ans = 0;
  for (auto i : lengths)
    for (auto j : i) {
      if (j != LONG_LONG_MAX)
        ans = max(j, ans);
    }
  cout << ans;
}

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