Submission #716289

#	Time	Username	Problem	Language	Result	Execution time	Memory
716289		nima_aryan	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	620 ms	111952 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   static int H, W;
   cin >> H >> W;
   static vector<string> snow(H);
   for (int i = 0; i < H; ++i) {
      cin >> snow[i];
   }
   const int inf = (int) 1e9;
   vector dist(H, vector<int>(W, inf));
   struct cell {
      int x, y;

      bool valid() {
         return x >= 0 && x < H && y >= 0 && y < W && snow[x][y] != '.';
      };
   };
   deque<cell> dq;
   auto ad = [&](cell c, int add, int extra = 0) {
      if (extra) {
         dq.push_back(c);
      }
      else {
         dq.push_front(c);
      }
      dist[c.x][c.y] = add + extra;
   };
   ad(cell{0, 0}, 1);
   vector<int> dx{1, -1, 0, 0};
   vector<int> dy{0, 0, 1, -1};
   int ans = 1;
   while (!dq.empty()) {
      auto c = dq.front();
      dq.pop_front();
      ans = max(ans, dist[c.x][c.y]);
      for (int i = 0; i < 4; ++i) {
         int x = c.x + dx[i], y = c.y + dy[i];
         auto newc = cell{x, y};
         if (!newc.valid() || dist[x][y] < inf) {
            continue;
         }
         ad(newc, dist[c.x][c.y], (int) (snow[x][y] != snow[c.x][c.y]));
      }
   }
   cout << ans << '\n';
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

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