제출 #700979

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
700979		phi	Tracks in the Snow (BOI13_tracks)	C++17	0 / 100	633 ms	215988 KiB

tracks

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

using namespace std;

vector<int> dx = { 1, 1, -1, -1 };
vector<int> dy = { 1, -1, 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 x, int y) {
        return 0 <= x && x < w && 0 <= y && y < h && snow[x][y] != '.';
    };

    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[x][y]);

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

    cout << ans - 1;

    return 0;
}

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