제출 #1291546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291546		hynmj	Tracks in the Snow (BOI13_tracks)	C++20	2.19 / 100	523 ms	144096 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;
    east.push({1, 1});
    int ans = 0;
    do
    {
        while (east.size())
        {
            auto t = east.back();
            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);
        ans++;
    } 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: 0 / 30
• Subtask 2: 2.1875 / 70