Submission #1276102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276102		nanaseyuzuki	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1006 ms	151728 KiB

tracks

#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 4e3 + 5, mod = 998244353, inf = 1e9;

int h, w, d[mn][mn], vis[mn][mn];
char a[mn][mn];

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

bool Megumi(int i, int j){
    if(i <= 0 || i >= h + 1 || j <= 0 || j >= w + 1) return false;
    if(a[i][j] == '.' || vis[i][j]) return false;
    return true;
}

void solve(){
    cin >> h >> w;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> a[i][j];
        }
    }
    fill(&d[0][0], &d[0][0] + mn * mn, inf);
    queue <pii> q1, q2;
    d[1][1] = 1;
    q1.push({1, 1});

    int res = 0;
    while(q1.size() || q2.size()){
        if(!q1.size()) swap(q1, q2);
        auto [i, j] = q1.front();
        q1.pop();
        res = max(res, d[i][j]);
        for(int k = 0; k < 4; k++){
            int ni = i + dx[k], nj = j + dy[k];
            if(!Megumi(ni, nj)) continue;
            vis[ni][nj] = true;
            if(a[ni][nj] == a[i][j]){
                if(d[ni][nj] > d[i][j]){
                    d[ni][nj] = d[i][j];
                    q1.push({ni, nj});
                }
            }
            else{
                if(d[ni][nj] > d[i][j] + 1){
                    d[ni][nj] = d[i][j] + 1;
                    q2.push({ni, nj});
                }
            }
        }
    }
    cout << res << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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