Submission #1269874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269874		picrad	Tracks in the Snow (BOI13_tracks)	C++20	89.06 / 100	2106 ms	193032 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,A[maxn][maxn],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] != '.' && !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][1] == '.'){
    cout << 0 << '\n';
    return 0;
  }
  vis[1][1] = 1;
  priority_queue<piii,vector<piii>,greater<piii>> pq;
  pq.push({1,{1,1}});
  while(!pq.empty()){
    auto cur = pq.top();
    pq.pop();
    int y = cur.se.fi, x = cur.se.se;;
    ans = max(ans,cur.fi);
    //cout << cur.fi << " " << y << " " << x  << '\n';
    A[y][x] = cur.fi;
    for(int i =0; i < 4; i++){
      int ny = y + dy[i],nx = x+dx[i];
      if(!valid(ny,nx))continue;
      pq.push({cur.fi + (S[y][x] == S[ny][nx] ? 0:1),{ny,nx}});
      vis[ny][nx] = 1;
    }
  }
  
  cout << ans << '\n';
  
}

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