Submission #1268540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268540		buzzy2	Tracks in the Snow (BOI13_tracks)	C++20	91.25 / 100	2112 ms	788596 KiB

tracks

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

vector<pair<int,int>> dirs = {{0,1},{1,0},{-1,0},{0,-1}};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<char>> v(n,vector<char>(m));
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) cin >> v[i][j];
    }

    vector<vector<int>> dist(n,vector<int>(m,-1));
    deque<vector<int>> q;
    q.push_front({0,0,0});

    while(!q.empty()) {
        int i = q.front()[0], j = q.front()[1], w = q.front()[2];
        q.pop_front();
        dist[i][j] = w;

        for(auto [a,b] : dirs) {
            int ni = a + i, nj = j + b;
            if(ni < 0 || nj < 0 || ni >= n || nj >= m || dist[ni][nj] != -1 || v[ni][nj] == '.') continue;
            
            if(v[ni][nj] != v[i][j]) {
                q.push_back({ni,nj,w+1});
            }
            else {
                q.push_front({ni,nj,w});
            }
        }
    }

    int ans = -1;
    for(vector<int>& i : dist) for(int j : i) ans = max(ans,j);
    cout<<ans+1<<endl;
}

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