Submission #1254475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254475		hoa208	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	681 ms	181980 KiB

tracks

#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N=4005;
const int INF=1e9;
#define fi first
#define se second
#define pa pair<int,int>
int h,w;
char a[N][N];
int was[N][N],d[N][N];
pa mov[]={{1,0},{0,1},{-1,0},{0,-1}};
bool out(int x,int y)
{
    return x>h || y>w || x<=0 || y<=0 || a[x][y]=='.' || was[x][y]==1;
}
int ans = 0;
void bfsX()
{
    memset(d, 0x3f,sizeof d);
    d[1][1] = 1;
    deque<pa> q;
    q.push_front({1, 1});
    was[1][1] = 1;
    while(!q.empty())
    {
        pa u = q.front();
        ans = max(ans, d[u.fi][u.se]);
        q.pop_front();
        for(int i = 0; i < 4; i ++)
        {
            pa v = {mov[i].fi + u.fi, mov[i].se + u.se};
            if(out(v.fi, v.se)) continue;
            was[v.fi][v.se] = 1;
            if(a[v.fi][v.se] != a[u.fi][u.se])
                q.push_back(v);
            else q.push_front(v);
            d[v.fi][v.se] = d[u.fi][u.se] + (a[v.fi][v.se] != a[u.fi][u.se]);
        }
    }
}
int main (void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>h>>w;
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            cin>>a[i][j];
    bfsX();
    cout<<ans;
    return 0;
}

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