Submission #997678

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

tracks

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

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

void bfs01(){
vector<vector<int>> depth(n+1,vector<int>(m+1,INT_MAX));
deque<pair<int,int>> dq;
depth[0][0]=1;
dq.push_back({0,0});
while(!dq.empty()){
    pair<int,int> u=dq.front();
    dq.pop_front();
    int i=u.first;
    int j=u.second;
    mini=max(mini,depth[i][j]); // maximalan depth
    for(int k=0;k<4;++k){
        int x=i+dx[k];
        int y=j+dy[k];
        if(check(x,y)){
            int c=(polja[x][y]==polja[i][j])?0:1;
            if(depth[x][y]>depth[i][j]+c){
                depth[x][y]=depth[i][j]+c; //relaxing
                if(c==0){
                    dq.push_front({x,y});
                }
                else{
                    dq.push_back({x,y});
                }
            }
        }
    }
}
}

int32_t 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];
    }
}
bfs01();
cout<<mini;
}

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