Submission #998393

#	Time	Username	Problem	Language	Result	Execution time	Memory
998393		Mil0S	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	430 ms	140736 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
const int maxn=4001;
char polja[maxn][maxn];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,m;
int depth[maxn][maxn];


bool check(int x,int y){
if(x<0)return 0;
if(y<0)return 0;
if(x>=n)return 0;
if(y>=m)return 0;
if(polja[x][y]=='.') return 0;
return 1;
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin>>n>>m;
  for(int i=0;i<n;++i){
    for(int j=0;j<m;++j){
        cin>>polja[i][j];
    }
  }
  deque<pair<int,int>> q;
  q.push_back({0,0});
int ans=0;
memset(depth,0,sizeof(depth));
depth[0][0]=1;
  while(!q.empty()) {
        pair<int,int> tren=q.front();
  q.pop_front();
    int x,y;
    x=tren.first;
    y=tren.second;
    ans=max(ans,depth[x][y]);
    for(int i=0;i<4;++i){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(check(nx,ny) && depth[nx][ny]==0){
                depth[nx][ny]=depth[x][y];
                if(polja[x][y]==polja[nx][ny]){
                    q.push_front({nx,ny});
                }
                else{
                         ++depth[nx][ny];
                    q.push_back({nx,ny});

                }
            }
    }
  }
  cout<<ans;
}

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