제출 #1278776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278776		eliminator_101	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	553 ms	144932 KiB

tracks

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

typedef long long ll;
const ll MAX = 4001, MOD = 1000000007;
ll t = 1, n, m, nx, ny, mx;
vector<string> v(MAX);
vector dist(MAX,vector<ll>(MAX, 1e9));


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("checklist.in", "r", stdin);
    //freopen("checklist.out", "w", stdout);
    //cin >>t;
    while(t--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> v[i];
        deque<pair<int, int>>q;
        q.push_front({1, 1});
        dist[1][1]=1;
        while(!q.empty()) {
            auto[x, y] = q.front();
            q.pop_front();
            for (int d = 0; d < 2; d++) {
                nx = x+d;
                ny = y+(1-d);
                if (nx>n||ny>n||v[nx][ny]=='.')continue;
                if (v[nx][ny]==v[x][y]&&dist[nx][ny]>dist[x][y]) {
                    dist[nx][ny]=dist[x][y];
                    q.push_front({nx, ny});
                }else if (dist[nx][ny]>dist[x][y]+1){
                    dist[nx][ny]=dist[x][y]+1;
                    q.push_back({nx, ny});
                }
            }
        }
        mx = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (dist[i][j]==1e9)continue;
                mx = max(mx, dist[i][j]);
            }
        }
        cout << mx << endl;
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

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