Submission #992098

#	Time	Username	Problem	Language	Result	Execution time	Memory
992098		MladenP	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	535 ms	139584 KiB

tracks

#include <iostream>
#include <string>
#include <deque>
using namespace std;

const int MAXN = 4002;
int cx[4] = {+1, 0, -1, 0};
int cy[4] = { 0,-1,  0,+1};
string s[MAXN];
int dist[MAXN][MAXN];

bool valid(int x, int y) { return (s[x][y] == 'R' || s[x][y] == 'F'); }

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int H, W; cin >> H >> W;
    s[0] = string(W+1, '#');
    for (int i = 1; i <= H; i++) {
        cin >> s[i];
        s[i] = '#' + s[i] + '#';
    }
    s[H+1] = string(W+1, '#');

    deque<pair<int, int> > dq;
    dq.push_front({1, 1});
    dist[1][1] = 1;
    int sol = 0;

    while (!dq.empty()) {
        pair<int, int> tp = dq.front(); dq.pop_front();
        int x = tp.first, y = tp.second;
        for (int dir = 0; dir < 4; dir++) {
            int nx = x+cx[dir];
            int ny = y+cy[dir];
            if (valid(nx, ny) && dist[nx][ny] == 0) {
                dist[nx][ny] = dist[x][y] + (s[x][y] != s[nx][ny]);
                sol = max(sol, dist[nx][ny]);
                if (s[x][y] != s[nx][ny]) {
                    dq.push_back({nx, ny});
                } else {
                    dq.push_front({nx, ny});
                }
            }
        }
    }

    cout << sol;
    return 0;
}

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