Submission #1319990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319990		vaderspader	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	767 ms	208788 KiB

tracks

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

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<vi> matrix;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define down(i, b, a) for(ll i = b - 1; i >= a; i--)

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll h, w;
    cin >> h >> w;

    vector<vector<char>> grid(h, vector<char>(w));
    rep(i, 0, h){
        rep(j, 0, w){
            cin >> grid[i][j];
        }
    }

    matrix dp(h, vi(w, 0));

    deque<pii> next;
    next.push_front({0, 0});

    dp[0][0] = 1;

    vi dx = {1, -1, 0, 0};
    vi dy = {0, 0, 1, -1};

    while(!next.empty()){
        pii top = next.front();
        next.pop_front();

        rep(i, 0, 4){
            ll x = top.first + dx[i], y = top.second + dy[i];

            if(x < 0 || x >= h || y < 0 || y >= w) continue;
            if(dp[x][y]) continue;
            if(grid[x][y] == '.') continue;

            if(grid[x][y] == grid[top.first][top.second]){
                dp[x][y] = dp[top.first][top.second];
                next.push_front({x, y});
            }
            else{
                dp[x][y] = dp[top.first][top.second] + 1;
                next.push_back({x, y});
            }
        }
    }

    ll best = 0;
    rep(i, 0, h){
        rep(j, 0, w){
            best = max(best, dp[i][j]);
        }
    }

    cout << best << endl;
}

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