Submission #1268223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268223		lamng3	Tracks in the Snow (BOI13_tracks)	C++20	0 / 100	1 ms	324 KiB

tracks

// problem url: https://oj.uz/problem/view/BOI13_tracks
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector< vector<int> > vii;

const int INF = 1e9+7;

int h, w;
vector<string> snow;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

bool inside(int x, int y) {
    if (x < 0 || x >= h || y < 0 || y >= w) return false;
    if (snow[x][y] == '.') return false;
    return true;
}

/*
inp:
5 8 
FFR..... 
.FRRR... 
.FFFFF.. 
..RRRFFR 
.....FFF
out:
2
*/
void solve() {
    cin >> h >> w;
    snow.reserve(h);
    for (int i = 0; i < h; i++) cin >> snow[i];
    int ans = 1;

    vii d(h, vi(w, INF));
    deque<pii> dq;
    dq.push_back(pii(0,0));
    d[0][0] = 1;
    while (!dq.empty()) {
        // auto [ux, uy] = dq.front() // for C++17
        pii u = dq.front();
        int ux = u.first, uy = u.second;
        dq.pop_front();
        ans = max(ans, d[ux][uy]);
        for (int i = 0; i < 4; i++) {
            int x = ux + dx[i], y = uy + dy[i];
            int w = snow[ux][uy] != snow[x][y];
            // what if: d[ux][uy] + w < d[x][y]
            // instead of d[x][y] == 0
            // answer: just based on initialization
            // it's better to use Dijkstra-style            
            if (!inside(x,y)) continue;
            if (d[ux][uy] + w < d[x][y]) {
                d[x][y] = d[ux][uy] + w;
                if (w) dq.push_back(pii(x,y));
                else dq.push_front(pii(x,y));
            }
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}

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