Submission #1093664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093664		akamizane	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	486 ms	136544 KiB

tracks

#include<bits/stdc++.h>
 
using namespace std;
 
 
using ll = long long;
using pii = pair<int,int>;
using ld = long double;
 
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){if (a < b) {a = b; return true;}return false;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){if (a > b) {a = b; return true;}return false;}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll mod = 1e9 + 7;

const int maxn = 5e5 + 5;

void solve(){
  int h, w;
  cin >> h >> w;
  string s[h];
  REP(i, h){
    cin >> s[i];
    cerr << s[i] << endl;
  }
  vector<vector<int>> dep(h, vector<int> (w));
  int dx[4] = {0, 0, -1, 1};
  int dy[4] = {-1, 1, 0, 0};
  deque<pii> dq;
  dq.push_back({0, 0});
  dep[0][0] = 1;
  int ans = 1;
  while(dq.size()){
    auto [a, b] = dq.front();
    dq.pop_front();
    chmax(ans, dep[a][b]);
    for (int i = 0; i < 4; i++){
      int x = a + dx[i];
      int y = b + dy[i];
      if (x < 0 || x >= h || y < 0 || y >= w) continue;
      if (s[x][y] == '.' || dep[x][y] != 0) continue;
      if (s[x][y] == s[a][b]){
        dep[x][y] = dep[a][b];
        dq.push_front({x, y});
      }
      else{
        dep[x][y] = dep[a][b] + 1;
        dq.push_back({x, y});
      }
    }
  }
  cout << ans;
}
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  //cin >> tests;
  for (int _ = 1; _ <= tests; _++){
    cerr << "- Case #" << _ << ": \n";
    solve();
    el;
  }
  return 0;
}

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