Submission #720325

#	Time	Username	Problem	Language	Result	Execution time	Memory
720325		Yell0	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	761 ms	50456 KiB

tracks

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
const int MN=4e3+2;
int H,W,ans=0;
char gr[MN][MN];
bool vis[MN][MN];

bool chk(int r,int c) {
  return r>0&&c>0&&r<=H&&c<=W&&gr[r][c]!='.'&&!vis[r][c];
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>H>>W;
  for(int i=1;i<=H;++i) cin>>(gr[i]+1);
  queue<pii> q,nq;
  q.push({1,1});
  vis[1][1]=1;
  while(1) {
    ++ans;
    while(!q.empty()) {
      int r=q.front().first,c=q.front().second;
      q.pop();
      if(chk(r+1,c)) {
        vis[r+1][c]=1;
        if(gr[r][c]==gr[r+1][c]) q.push({r+1,c});
        else nq.push({r+1,c});
      }
      if(chk(r-1,c)) {
        vis[r-1][c]=1;
        if(gr[r][c]==gr[r-1][c]) q.push({r-1,c});
        else nq.push({r-1,c});
      }
      if(chk(r,c+1)) {
        vis[r][c+1]=1;
        if(gr[r][c]==gr[r][c+1]) q.push({r,c+1});
        else nq.push({r,c+1});
      }
      if(chk(r,c-1)) {
        vis[r][c-1]=1;
        if(gr[r][c]==gr[r][c-1]) q.push({r,c-1});
        else nq.push({r,c-1});
      }
    }
    swap(nq,q);
    if(q.empty()) break;
  }
  cout<<ans<<'\n';
  return 0;
}

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