Submission #1122859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122859		barkolorious	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1413 ms	334000 KiB

tracks

// barkolorious - 01 December 2024
// in god, do we trust? 
#include <bits/stdc++.h>
using namespace std;

#define FIN(x) freopen(x ".in", "r", stdin)
#define FOUT(x) freopen(x ".out", "w", stdout)
#define int long long
#define pb  push_back
#define fr  first
#define sc  second
#define __  << " " << 

const int N = 4e3 + 5;
char snow[N][N];
int dist[N][N], vis[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int w, h;

bool check (int x, int y) {
  return (1 <= x && x <= w) && (1 <= y && y <= h);
}

void solve () {
  cin >> h >> w;
  for (int y = 1; y <= h; y++) {
    for (int x = 1; x <= w; x++) {
      cin >> snow[x][y];
    }
  }

  deque<pair<int, int>> dq;
  dq.push_front({1, 1});
  dist[1][1] = 1;
  vis[1][1] = true;
  int ans = 1;

  while (!dq.empty()) {
    int x = dq.front().fr, y = dq.front().sc;
    dq.pop_front();
    ans = max(ans, dist[x][y]);
    // cout << x __ y << endl;

    for (int i = 0; i < 4; i++) {
      int xx = x + dx[i], yy = y + dy[i];

      if (!check(xx, yy)) continue;
      if (snow[xx][yy] == '.') continue;
      if (vis[xx][yy]) continue;
      
      vis[xx][yy] = true;

      if (snow[x][y] == snow[xx][yy]) {
        dist[xx][yy] = dist[x][y];
        dq.push_front({xx, yy});
      } else {
        dist[xx][yy] = dist[x][y] + 1;
        dq.push_back({xx, yy});
      }
    }
  }
  cout << ans << endl;
}

/*
-- Sample 1 --
Input:
5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF
Output:
2
*/

/*
g++ -std=c++17 -O2 -Wall -DLOCAL "C:\Users\LENOVO\Desktop\BARKIN\Genel\Programming\Competitive\Questions\Olympiads\BOI13\BOI13_tracks.cpp" -o _run
*/

int32_t main () {
  #ifndef LOCAL
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
  #endif

  #ifdef LOCAL
    clock_t __START__ = clock();
    FILE* __FILE_IN__ = FIN("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
    FILE* __FILE_OUT__ = FOUT("C:/Users/LENOVO/Desktop/BARKIN/Genel/Programming/Competitive/_run");
  #endif

  solve();

  #ifdef LOCAL
    fclose(__FILE_IN__);
    fclose(__FILE_OUT__);
    cerr << "Executed in: " << fixed << setprecision(3) << (double) (clock() - __START__) / CLOCKS_PER_SEC << "seconds" << endl;
  #endif

  return 0;
}

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