Submission #700980

#	Time	Username	Problem	Language	Result	Execution time	Memory
700980		phi	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	1060 ms	112196 KiB

tracks

#include <vector>
#include <utility>
#include <iostream>
#include <string>
#include <deque>
#include <cmath>

using namespace std;

vector<int> dx = { 1, -1, 0, 0 };
vector<int> dy = { 0, 0, 1, -1 };

int main() {
    int h, w;
    cin >> h >> w;

    vector<string> snow(h);
    for (int i = 0; i < h; i++) cin >> snow[i];

    vector<vector<int>> depth(h, vector<int>(w));

    auto inside = [&](int y, int x) {
        return 0 <= x && x < w && 0 <= y && y < h && snow[y][x] != '.';
    };

    int ans = 1;

    deque<pair<int, int>> visit;
    visit.push_back({ 0, 0 });
    depth[0][0] = 1;

    while (!visit.empty()) {
        auto [ x, y ] = visit.front();
        visit.pop_front();

        ans = max(ans, depth[y][x]);

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (inside(ny, nx) && depth[ny][nx] == 0) {
                if (snow[y][x] == snow[ny][nx]) {
                    depth[ny][nx] = depth[y][x];
                    visit.push_front({ nx, ny });
                } else {
                    depth[ny][nx] = depth[y][x] + 1;
                    visit.push_back({ nx, ny });
                }
            }
        }
    }

    cout << ans;

    return 0;
}

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