Submission #635622

#	Time	Username	Problem	Language	Result	Execution time	Memory
635622		thienbao1602	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	745 ms	33604 KiB

tracks

#include    <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;

const int u[] = {0, 1, 0, -1};
const int v[] = {1 , 0, -1, 0};
const int N = 4055;

int W, H;
char snow[N][N];

bool safe(int u, int v)
{
    return (u >= 0 && u < W && v >= 0 && v < H);
}

void solve()
{
    cin >> W >> H;
    for(int row=0; row<W; row++)
    {
        for(int col=0; col<H; col++)
        {
            cin >> snow[row][col];
        }
    }

    queue<pair<int, int>> que[2];
    int num = 0;
    que[num & 1].push(make_pair(W - 1, H - 1));
    char track = snow[W - 1][H - 1];
    snow[W - 1][H - 1] = '#';

    while(!que[num & 1].empty())
    {
        int rest = 1 - (num & 1);
        int cur = num & 1;
        while(!que[cur].empty())
        {
            pair<int, int> now = que[cur].front();
            que[cur].pop();
            int curU = now.fi, curV = now.se;
            for(int i=0; i<4; i++)
            {
                int ux = curU + u[i], vx = curV + v[i];
                if (safe(ux, vx))
                {
                    if (snow[ux][vx] == track)
                    {
                        que[cur].push(make_pair(ux, vx));
                        snow[ux][vx] = '#';

                    } else
                    {
                        if (snow[ux][vx] != '.' && snow[ux][vx] != '#')
                        {
                            que[rest].push(make_pair(ux, vx));
                            snow[ux][vx] = '#';
                        }
                    }
                }
            }
        }
        track = (track == 'F' ? 'R' : 'F');
        num++;
    }
    cout << num;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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