Submission #1254487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254487		satyanshu	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	671 ms	121556 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 998244353;
const ll INF = 1e9 + 7;

bool is_valid(int x, int y, int n, int m)
{
    return x >= 0 && x < n && y >= 0 && y < m;
}

void solve()
{
    int H, W;
    cin >> H >> W;

    vector<string> a(H);
    for (int i = 0; i < H; i++)
    {
        cin >> a[i];
    }
    
    deque<pair<int, int>> q;
    vector<vector<int>>dis(H, vector<int>(W, INF));
    int ans = 1;
    q.push_front({0, 0});
    dis[0][0] = 1;

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop_front();

        int del_x[4] = {-1, 0, 0, 1};
        int del_y[4] = {0, -1, 1, 0};

        for (int i = 0; i < 4; i++)
        {
            int new_x = x + del_x[i];
            int new_y = y + del_y[i];

            if (is_valid(new_x, new_y, H, W) && a[new_x][new_y] != '.')
            {
                if (a[new_x][new_y] == a[x][y] && dis[new_x][new_y] > dis[x][y])
                {
                    dis[new_x][new_y] = dis[x][y];
                    q.push_front({new_x, new_y});
                }
                else if (a[new_x][new_y] != a[x][y] && dis[new_x][new_y] > dis[x][y] + 1)
                {
                    dis[new_x][new_y] = dis[x][y] + 1;
                    q.push_back({new_x, new_y});
                }
            }
        }
    }

    cout << dis[H - 1][W - 1] + 1<< endl;
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

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