Submission #862600

#	Time	Username	Problem	Language	Result	Execution time	Memory
862600		neodoomer	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	522 ms	141152 KiB

tracks

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define pi pair<int,int>
const int N=4010;
int n,m,vis[N][N],ans;
char g[N][N];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
bool good (int i,int j)
{
    return (i>-1 && j>-1 && i<n && j<m && g[i][j]!='.');
}
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>g[i][j];
    memset(vis,-1,sizeof vis);
    deque<pi> dq;
    dq.pb({0,0});vis[0][0]=0;
    while(!dq.empty()){
        int i=dq.front().F,j=dq.front().S;
        ans=max(ans,vis[i][j]);
        dq.pop_front();
        for(int d=0;d<4;d++)
        {
            int ni=i+dx[d],nj=j+dy[d];
            if(!good(ni,nj) || vis[ni][nj]!=-1)continue;
            int w=(g[i][j]!=g[ni][nj]? 1:0);
            vis[ni][nj]=w+vis[i][j];
            if(w)dq.pb({ni,nj});
            else dq.push_front({ni,nj});
        }
    }
    cout<<ans+1;

    return 0;
}

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