Submission #703026

#	Time	Username	Problem	Language	Result	Execution time	Memory
703026		David8406	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	856 ms	200868 KiB

tracks

#include <bits/stdc++.h>
#define INF 999999999
#define mod 3000017
using namespace std;
int n,m,viz[4005][4005],dist[4005][4005];
string a[4005];
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
struct point{
    int x,y;
};
deque <point> q;
int lee(){
    viz[0][0]=1;
    dist[0][0]=1;
    q.push_back({0,0});
    while (!q.empty()){
        point x=q.front();
        q.pop_front();
        for(int d=0;d<4;d++){
            point newx={dx[d]+x.x,dy[d]+x.y};
            if (newx.x>=0 && newx.y>=0 && newx.x<n && newx.y<m)
                if (!viz[newx.x][newx.y])
                    if (a[newx.x][newx.y]!='.'){
                        viz[newx.x][newx.y]=1;
                        if (a[x.x][x.y]==a[newx.x][newx.y]){
                            dist[newx.x][newx.y]=dist[x.x][x.y];
                            q.push_front(newx);
                        }
                        else{
                            dist[newx.x][newx.y]=dist[x.x][x.y]+1;
                            q.push_back(newx);
                        }
                    }
        }
    }
    int mx=0;
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            mx=max(mx,dist[i][j]);
    return mx;
}
int main(){
    cin>>n>>m;
    for (int i=0;i<n;i++) cin>>a[i];
    cout<<lee();
}

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