Submission #931377

#	Time	Username	Problem	Language	Result	Execution time	Memory
931377		sofija6	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1132 ms	121764 KiB

tracks

#include <bits/stdc++.h>
#define ll int
#define MAXN 4001
using namespace std;
char c[MAXN][MAXN];
ll dist[MAXN][MAXN];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll h,w;
    cin >> h >> w;
    for (ll i=1;i<=h;i++)
    {
        for (ll j=1;j<=w;j++)
            cin >> c[i][j];
    }
    deque<pair<ll,ll> > q;
    q.push_back({1,1});
    dist[1][1]=1;
    ll ans=0;
    while (!q.empty())
    {
        ll i=q.front().first,j=q.front().second;
        q.pop_front();
        ans=max(ans,dist[i][j]);
        vector<pair<ll,ll> > same,diff;
        for (ll x=-1;x<2;x++)
        {
            for (ll y=-1;y<2;y++)
            {
                if (abs(x)+abs(y)==1 && (c[i+x][j+y]=='R' || c[i+x][j+y]=='F') && !dist[i+x][j+y])
                {
                    dist[i+x][j+y]=dist[i][j]+(c[i+x][j+y]!=c[i][j]);
                    if (c[i+x][j+y]!=c[i][j])
                        diff.push_back({i+x,j+y});
                    else
                        same.push_back({i+x,j+y});
                }
            }
        }
        for (auto x : same)
            q.push_front(x);
        for (auto x : diff)
            q.push_back(x);
    }
    cout << ans;
    return 0;
}

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