Submission #1291548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291548		hynmj	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	991 ms	161808 KiB

tracks

#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long N = 4e3 + 5;
int a[N][N];
bool seen[N][N];
int n, m;
bool valid(int i, int j)
{
    if (i < 0 or i >= n or j < 0 or j >= m or seen[i][j])
        return 0;
    return 1;
}

void solve()
{
    cin >> n >> m;
    char c;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> c;
            if (c == 'F')
                a[i][j] = 0;
            else if (c == '.')
                seen[i][j] = 1;
            else
                a[i][j] = 1;
        }
    }
    queue<pair<int, int>> east, west;
    int my, them;
    my = a[0][0];
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    them = 1 ^ my;

    // for (int i = 0; i < n; i++)
    // {
    //     for (int j = 0; j < m; j++)
    //     {
    //         cout << a[i][j] << ' ';
    //     }
    //     cout << endl;
    // }
    // cout << endl;
    east.push({0, 0});
    int ans = 0;
    do
    {
        while (east.size())
        {
            auto t = east.front();
            east.pop();
            for (int i = 0; i < 4; i++)
            {
                int fx, fy;
                fx = t.first + dx[i], fy = t.second + dy[i];
                if (valid(fx, fy))
                {
                    if (my == a[fx][fy])
                    {
                        east.push({fx, fy});
                        seen[fx][fy] = 1;
                    }
                    else
                    {
                        west.push({fx, fy});
                        seen[fx][fy] = 1;
                    }
                }
            }
        }
        swap(east, west);
        swap(my, them);
        ans++;
        // for (int i = 0; i < n; i++)
        // {
        //     for (int j = 0; j < m; j++)
        //     {
        //         cout << seen[i][j] << ' ';
        //     }
        //     cout << endl;
        // }
        // cout << endl;

    } while (east.size());
    cout << ans << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << ':' << ' ';
        solve();
        cout << endl;
    }
    return 0;
}

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