Submission #1270440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270440		picrad	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	420 ms	175832 KiB

tracks

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long ll;
typedef double dbl;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
const int maxn = 4e3+5;
ll H,W,ans,dy[4] = {1,-1,0,0},dx[4] = {0,0,1,-1};
bool vis[maxn][maxn];
string S[maxn];

bool valid(int y, int x){
  return y > 0 && x > 0 && y <= H && x <= W && S[y][x-1] != '.' && !vis[y][x];
}


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> H >> W;
  for(int i =1; i <= H; i++){
    cin >> S[i];
    //S[i] = " "+S[i];
  }
  if(S[1][0] == '.'){
    cout << 0 << '\n';
    return 0;
  }
  vis[1][1] = 1;
  deque<piii> dq;
  dq.emplace_front(piii(1, pii(1, 1)));
  while(!dq.empty()){
    piii cur = *dq.begin();
    dq.pop_front();
    int y = cur.se.fi, x = cur.se.se;
    ans = max(ans,cur.fi);
    for(int i =0; i < 4; i++){
      int ny = y + dy[i],nx = x+dx[i];
      if(!valid(ny,nx))continue;
      if(S[y][x-1] == S[ny][nx-1] )dq.emplace_front(piii(cur.fi, pii(ny, nx)));
      else dq.emplace_back(piii(cur.fi+1, pii(ny, nx)));
      vis[ny][nx] = 1;
    }
  }
  
  cout << ans << '\n';
  
}

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