제출 #1136644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1136644		unreached7534	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	812 ms	113584 KiB

tracks

#include <iostream>
#include <deque>
#include <vector>
#include <array>
#include <utility>

const std::array<std::pair<int, int>, 4> DIR = {{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}};

int main() {
    int H, W;
    std::cin >> H >> W;
    using std::vector;
    vector<vector<char>> snow(H, vector<char>(W));
    for (auto& i : snow) {
        for (char& j : i) {
            std::cin >> j;
        }
    }
    int ans = 0;
    vector<vector<int>> depth(H, vector<int>(W));
    depth[0][0] = 1;
    std::deque<std::pair<int, int>> bfs{{0, 0}};
    while (!bfs.empty()) {
        int x = bfs.front().first, y = bfs.front().second;
        bfs.pop_front();
        ans = std::max(ans, depth[x][y]);
        for (const auto& [dx, dy] : DIR) {
            int nx = x + dx, ny = y + dy;
            if (nx < 0 || nx == H || ny < 0 || ny == W || snow[nx][ny] == '.' || depth[nx][ny] != 0) {
                continue;
            }
            if (snow[nx][ny] == snow[x][y]) {
                bfs.emplace_front(nx, ny);
                depth[nx][ny] = depth[x][y];
            }
            else {
                bfs.emplace_back(nx, ny);
                depth[nx][ny] = depth[x][y] + 1;
            }
        }
    }
    std::cout << ans << "\n"; 
}

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