제출 #1317925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317925		mousham	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	371 ms	118696 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

/*
In this question, every valid animal path starts at (1,1) and ends at (N,M)
So any path that reaches any cell (x,y) can be extended to (N,M).

answer= max​ of (min​ component switches on path P) over all paths P from (1, 1) to any other cell
now this max is from (1, 1) to (N, M) always
*/

constexpr char UNTOUCHED('.');
constexpr int DIRNS(4);
constexpr int MAX_SIZE(4000);

constexpr int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};
int n, m, ans = 1, depth[MAX_SIZE][MAX_SIZE]; // depth[i][j] = min no. of animals required to reach cell (i, j) from (0, 0) including (0, 0) and (i, j) = 1 + min. no of letter changes along any valid path from (0, 0) to (i, j)
string snow[MAX_SIZE];                        // input to be taken over here

// Checks whether cell inside snow grid
inline bool inside(int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m && snow[x][y] != UNTOUCHED); }

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

    cin >> n >> m; // n, m are globally declared where n is height and m is width
    for (int i = 0; i < n; i++)
        cin >> snow[i];

    deque<pair<int, int>> q;
    q.emplace_back(0, 0);
    depth[0][0] = 1;

    while (!q.empty())
    {
        auto [cx, cy] = q.front();
        q.pop_front();

        // Track maximum animals needed so far
        ans = max(ans, depth[cx][cy]);

        // Explore 4 neighboring cells
        for (int d = 0; d < DIRNS; d++)
        {
            int nx = cx + dx[d], ny = cy + dy[d];

            // If neighbor is valid and not yet visited (depth == 0 means univisted)
            if (inside(nx, ny) && depth[nx][ny] == 0)
            {
                if (snow[nx][ny] == snow[cx][cy]) // Same animal
                {
                    depth[nx][ny] = depth[cx][cy];
                    q.emplace_front(nx, ny);
                }
                else
                {
                    depth[nx][ny] = depth[cx][cy] + 1;
                    q.emplace_back(nx, ny);
                }
            }
        }
    }

    cout << ans;
}

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