Submission #577571

#	Time	Username	Problem	Language	Result	Execution time	Memory
577571		ThinGarfield	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	1389 ms	130956 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define mp make_pair
#define F first
#define S second

constexpr int maxn = 4000;

int h, w;
char grid[maxn][maxn];

int dist[maxn][maxn];
pii dir[4] = {mp(1, 0), mp(-1, 0), mp(0, 1), mp(0, -1)};
deque<pii> q;

pii vsum(pii a, pii b) { return mp(a.F + b.F, a.S + b.S); }

int main() {
  // ios_base::sync_with_stdio(false);
  // cin.tie(NULL);

  cin >> h >> w;

  for (int r = 0; r < h; r++) {
    for (int c = 0; c < w; c++) {
      cin >> grid[r][c];
      dist[r][c] = maxn * maxn;
    }
  }

  //   for (auto p : dir) cout << p.F << ' ' << p.S << '\n';

  dist[0][0] = 0;
  q.push_front(mp(0, 0));
  while (!q.empty()) {
    pii cell = q.front();
    q.pop_front();
    for (int i = 0; i < 4; i++) {
      pii nbr = vsum(cell, dir[i]);
      if (nbr.F < 0 || nbr.F >= h || nbr.S < 0 || nbr.S >= w) continue;
      if (grid[nbr.F][nbr.S] == '.') continue;
      int wgt = (grid[cell.F][cell.S] == grid[nbr.F][nbr.S] ? 0 : 1);
      //   cout << "checked " << cell.F << cell.S << " " << nbr.F << nbr.S << '\t' << wgt << '\n';
      if (dist[cell.F][cell.S] + wgt < dist[nbr.F][nbr.S]) {
        dist[nbr.F][nbr.S] = dist[cell.F][cell.S] + wgt;
        if (wgt == 1)
          q.push_back(nbr);
        else
          q.push_front(nbr);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      //   cout << (dist[i][j] == maxn * maxn ? -1 : dist[i][j]) << '\t';
      if (grid[i][j] != '.') ans = max(ans, dist[i][j]);
    }
    // cout << '\n';
  }
  cout << ans + 1 << '\n';

  return 0;
}

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