Submission #101619

#	Time	Username	Problem	Language	Result	Execution time	Memory
101619		ShaneOng	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1078 ms	119328 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

int h,w,dist[4009][4009],dx[]={0,1,0,-1},dy[]={1,0,-1,0},ans;
char grid[4009][4009];

int main(){
    scanf("%d%d",&h,&w);
    for(int x=0;x<h;x++)
        scanf("%s",&grid[x]);
    for(int x=0;x<h;x++)
        for(int y=0;y<w;y++)
            dist[x][y]=-1;
    deque<ii> dq;
    dq.push_front(ii(0,0));
    dist[0][0]=0;
    while(!dq.empty()){
        int ux=dq.front().first,uy=dq.front().second;
        dq.pop_front();
        for(int i=0;i<4;i++){
            int vx=ux+dx[i],vy=uy+dy[i];
            if(vx>=0&&vx<h&&vy>=0&&vy<w)
                if(grid[vx][vy]!='.'){
                    int val=(grid[ux][uy]!=grid[vx][vy]);
                    if(dist[vx][vy]==-1){
                        dist[vx][vy]=dist[ux][uy]+val;
                        //printf("%d,%d:%d\n",vx,vy,dist[vx][vy]);
                        ans=max(dist[vx][vy],ans);
                        if(val==0)
                            dq.push_front(ii(vx,vy));
                        else
                            dq.push_back(ii(vx,vy));
                    }
                }
        }
    }
    printf("%d\n",ans+1);
}

Compilation message (stderr)

tracks.cpp: In function 'int main()':
tracks.cpp:11:28: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[4009]' [-Wformat=]
         scanf("%s",&grid[x]);
                    ~~~~~~~~^
tracks.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&h,&w);
     ~~~~~^~~~~~~~~~~~~~
tracks.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&grid[x]);
         ~~~~~^~~~~~~~~~~~~~~

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