Submission #1269246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269246		sashimivssushi	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	516 ms	119036 KiB

tracks

#include <bits/stdc++.h>
#define ll long long
#define sti string
#define vt vector
#define INF ((int) 1e9)
#define MOD 1000000007
#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define dbg(x) cerr << #x << " = " << x << '\n';
#define bit(mask, i) ((mask >> i) & 1)
#define fi first
#define sc second
#define MAXXTEST 100
#define MAXN 4000
#define MAXNTEST 100
#define SOTEST 100

using namespace std;

const sti name = "";

inline void stress_test ()
{

}

inline void file ()
{
    freopen((name + ".inp").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
}

char a[MAXN + 5][MAXN + 5];
int D[MAXN + 5][MAXN + 5],
dx[] = {0, 0, -1, 1},
dy[] = {1, -1, 0, 0},
H, W;

inline bool check(int x, int y)
{
    return 1 <= x && x <= H && 1 <= y && y <= W && a[x][y] != '.';
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> H >> W;
    for (int i = 1; i <= H; ++i)
        for (int j = 1; j <= W; ++j)
        {
            cin >> a[i][j];
            D[i][j] = INF;
        }
    deque<pii> dq;
    D[1][1] = 0;
    dq.emplace_back(1, 1);
    while (!dq.empty())
    {
        auto u = dq.front();
        int i = u.fi, j = u.sc;
        dq.pop_front();
        for (int k = 0; k < 4; ++k)
        {
            int x = i + dx[k], y = j + dy[k];
            bool v = a[i][j] != a[x][y];
            if (check(x, y) && D[x][y] > D[i][j] + v)
            {
                D[x][y] = D[i][j] + v;
                if (v == 1) dq.emplace_back(x, y);
                else dq.emplace_front(x, y);
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= H; ++i)
        for (int j = 1; j <= W; ++j)
            if (D[i][j] != INF)
                ans = max(ans, D[i][j]);
    cout << ans + 1;




    return 0;
}

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