제출 #1124042

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1124042		kustizus	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	774 ms	156736 KiB

tracks

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

#define fi first
#define se second
#define sz(s) (int)s.size()
#define bit(i, j) ((j >> i) & 1)
#define all(v) v.begin(), v.end()
#define taskname "file"

typedef long long ll;

const int N = 4e3;
int n, m, d[N + 5][N + 5];
char a[N + 5][N + 5];
bool vs[N + 5][N + 5];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct node{
    int val, x, y;
};
deque <node> dq;

void solve(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> a[i][j];
    d[1][1] = 1;
    vs[1][1] = true;
    dq.push_back({1, 1, 1});
    int ans = 0;
    while (sz(dq)){
        node x = dq.back();
        dq.pop_back();
        ans = max(ans, x.val);
        for (int k = 0; k < 4; ++k){
            int i = x.x + dx[k];
            int j = x.y + dy[k];
            if (i < 1 || i > n || j < 1 || j > m) continue;
            if (vs[i][j]) continue;
            if (a[i][j] == '.') continue;
            vs[i][j] = true;
            d[i][j] = x.val + (a[i][j] != a[x.x][x.y]);
            if (d[i][j] != x.val) dq.push_front({d[i][j], i, j});
            else dq.push_back({d[i][j], i, j});
        }
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen(taskname".inp", "r", stdin);
    // freopen(taskname".out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
}

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