Submission #553769

#	Time	Username	Problem	Language	Result	Execution time	Memory
553769		Uzouf	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1433 ms	348148 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
//#define endl "\n"
const int mod = (int) 1e9 + 7;
const int N=4005;

int n,m,ans,nm;
char c,tmp;
char v[N][N];
int cst[N][N];
bool vis[N][N];
bool bl;

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

bool chk(int i,int j) {
  return i>=0 && j>=0 && i<n && j<m && !vis[i][j] && v[i][j]!='.';
}

void bfs() {
  deque<pair<int,int> > q; q.push_front({0,0});
  while (!q.empty()) {
    int i=q.front().first;
    int j=q.front().second;
    q.pop_front();
    vis[i][j]=true;
    ans=max(ans,cst[i][j]);

    for (int p=0;p<4;p++) {
      int ii=i+dx[p],jj=j+dy[p];

      if (chk(ii,jj)) {
      if (v[i][j]==v[ii][jj]) {cst[ii][jj]=cst[i][j]; q.push_front({ii,jj});}
      else {cst[ii][jj]=cst[i][j]+1;q.push_back({ii,jj});}
      }

    }
  }

}


signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(".in", "r", stdin); freopen(".out", "w", stdout);

    cin>>n>>m;
    for (int i=0;i<n;i++) {
      for (int j=0;j<m;j++) {
        cin>>v[i][j];
      }
    }

    cst[0][0]=1; bfs();
    cout<<ans;
}

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