Submission #1047415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047415		coin_	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	451 ms	122980 KiB

tracks

// This template is based on - Baltic OI 2013 - Tracks in the Snow
// this is basically dijstra, but seems pretty dang cool

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

int dx[4] = {0, 0, 1, -1};
int dy[4] = {-1, 1, 0, 0};

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    int h, w;
    cin >> h >> w;
    vector<vector<char>> board(h+5, vector<char>(w+5));
    vector<vector<int>> level(h+5, vector<int>(w+5, -1));
    for (int i = 1; i <= h; i++){
        for (int j = 1; j <= w; j++){
            cin >> board[i][j];
        }
    }
    deque<pair<int, int>> q;
    q.push_back({1, 1});
    level[1][1] = 1;
    int ans = 0;
    while (!q.empty()){
        pair<int, int> u = q.front();
        q.pop_front();
        int x = u.first, y = u.second;
        ans = max(ans, level[y][x]);
        for (int k = 0; k < 4; k++){
            int tx = x + dx[k], ty = y + dy[k];
            if (tx <= 0 || ty <= 0 || tx > w || ty > h || board[ty][tx] == '.' || level[ty][tx] != -1) continue;
            if (board[y][x] == board[ty][tx]){
                level[ty][tx] = level[y][x];
                q.push_front({tx, ty});
            }
            else{
                level[ty][tx] = level[y][x] + 1;
                q.push_back({tx, ty});
            }
        }
    }
    cout << ans;
}

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