제출 #931375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
931375		sofija6	Tracks in the Snow (BOI13_tracks)	C++14	29.58 / 100	1209 ms	94596 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];
    }
    queue<pair<ll,ll> > q;
    q.push({1,1});
    dist[1][1]=1;
    ll ans=0;
    while (!q.empty())
    {
        ll i=q.front().first,j=q.front().second;
        q.pop();
        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(x);
        for (auto x : diff)
            q.push(x);
    }
    cout << ans;
    return 0;
}

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