Submission #719262

#	Time	Username	Problem	Language	Result	Execution time	Memory
719262		thimote75	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	839 ms	155244 KiB

tracks

#include <bits/stdc++.h>

using namespace std;

#define idata vector<int>
#define imap vector<idata>

#define EMPTY -1
#define FOX 0
#define RABBIT 1

#define di pair<int, int>

imap positions;
int height, width;

imap visited;
int stage = 1;

void try_add (deque<di> &dq, int x, int y, int nx, int ny) {
    if (positions[nx][ny] == EMPTY) return ;
    if (visited  [nx][ny] != EMPTY) return ;
    int valuation = positions[nx][ny] == positions[x][y] ? 0 : 1;

    visited[nx][ny] = visited[x][y] + valuation;
    if (valuation == 0) dq.push_front({ nx, ny });
    if (valuation == 1) dq.push_back ({ nx, ny });
}

int bfs () {
    deque<di> point_queue;
    point_queue.push_front({ 0, 0 });

    visited[0][0] = 1;

    int max_stage = 0;
    while (point_queue.size() != 0) {
        di meta = point_queue.front();
        point_queue.pop_front();

        int x, y; x = meta.first; y = meta.second;
        max_stage = max(max_stage, visited[x][y]);
    
        if (x != 0) try_add(point_queue, x, y, x - 1, y);
        if (y != 0) try_add(point_queue, x, y, x, y - 1);
        if (x != height - 1) try_add(point_queue, x, y, x + 1, y);
        if (y != width  - 1) try_add(point_queue, x, y, x, y + 1);
    }

    return max_stage;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> height >> width;

    positions.resize( height, idata(width, EMPTY) );
    visited  .resize( height, idata(width, EMPTY) );

    for (int h = 0; h < height; h ++) {
        string buffer;
        cin >> buffer;

        for (int w = 0; w < width; w ++) {
            int mu = EMPTY;
            if (buffer[w] == 'F') mu = FOX;
            if (buffer[w] == 'R') mu = RABBIT;

            positions[h][w] = mu;
        }
    }

    cout << bfs();
}

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