Submission #1062967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062967		v_matei	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	467 ms	128344 KiB

tracks

#include <bits/stdc++.h>
#include <deque>

#define ll long long
#define ull unsigned long long
#define pii std::pair<int, int>

#define IO (std::string) ""
std::ifstream fin(IO + ".in");
std::ofstream fout(IO + ".out");

#define NMAX 4001
#define INF INT_MAX
int di[] = {1, -1, 0, 0}, dj[] = {0, 0, 1, -1};

int h, w;
char map[NMAX][NMAX];

void citire() {
  std::cin >> h >> w;
  for (int i = 0; i < h; i++)
    std::cin >> map[i];
}

int dist[NMAX][NMAX];

bool inside(int i, int j) {
  return (i > -1 && i < h && j > -1 && j < w && map[i][j] != '.');
}

int bfs01() {
  std::deque<pii> q;
  q.push_back({0, 0});
  dist[0][0] = 1;
  int ans = 1;
  while (q.size()) {
    pii c = q.front();
    q.pop_front();
    ans = std::max(ans, dist[c.first][c.second]);

    for (int i = 0; i < 4; i++) {
      int x = c.first + di[i], y = c.second + dj[i];
      if (inside(x, y) && dist[x][y] == 0) {
        if (map[x][y] == map[c.first][c.second]) {
          dist[x][y] = dist[c.first][c.second];
          q.push_front({x, y});
        } else {
          dist[x][y] = dist[c.first][c.second] + 1;
          q.push_back({x, y});
        }
      }
    }
  }
  return ans;
}

int main() {
  std::cin.tie(0)->std::ios::sync_with_stdio(0);
  citire();
  std::cout << bfs01();
  return 0;
}

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