Submission #530288

#	Time	Username	Problem	Language	Result	Execution time	Memory
530288		raypeng1729	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	763 ms	220776 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
const int N = 2e5 + 5, MOD = 1e9 + 7, INF = 1e9;
#define X first
#define Y second
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> dis(n, vector<int>(m, INF));
    vector<vector<char>> c(n, (vector<char>(m)));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> c[i][j];
        }   
    }
    deque<pair<int, int>> dq;
    int ans = 0;
    dq.push_back({0, 0});
    dis[0][0] = 1;
    auto check = [&](int i, int j, int x, int y){
        if(c[i][j] == '.' || dis[i][j] != INF) return;
        if(c[i][j] == c[x][y]) dis[i][j] = dis[x][y], dq.push_front({i, j});
        else dis[i][j] = dis[x][y] + 1, dq.push_back({i, j});
    };
    while(dq.size()){
        auto i = dq.front(); dq.pop_front();
        int I = i.X, J = i.Y;
        if(I < n - 1) check(I + 1, J, I, J);
        if(I) check(I - 1, J, I, J);
        if(J < m - 1)check(I, J + 1, I, J);
        if(J) check(I, J - 1, I, J);
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
        if(dis[i][j] != INF) ans = max(ans, dis[i][j]);
    }
    cout << ans;
}

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