Submission #445084

#	Time	Username	Problem	Language	Result	Execution time	Memory
445084		MilosMilutinovic	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	673 ms	120224 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
const int N=4050;
const int inf=1e9;
int n,m,dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
char s[N][N];
int dist[N][N];
bool valid(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]!='.';
}
int main(){
    scanf("%i%i",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dist[i][j]=inf;
    deque<pair<int,int>> q;
    q.push_back({1,1});
    dist[1][1]=1;
    while(!q.empty()){
        int x=q[0].first;
        int y=q[0].second;
        q.pop_front();
        for(int dir=0;dir<4;dir++){
            int nx=x+dx[dir],ny=y+dy[dir];
            int w=(s[x][y]!=s[nx][ny]);
            if(valid(nx,ny)&&dist[nx][ny]>dist[x][y]+w){
                dist[nx][ny]=dist[x][y]+w;
                if(w==0)q.push_front({nx,ny});
                else q.push_back({nx,ny});
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(dist[i][j]!=inf)ans=max(ans,dist[i][j]);
    printf("%i",ans);
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%i%i",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:13:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
      |                          ~~~~~^~~~~~~~~~~~~

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