Submission #719251

#	Time	Username	Problem	Language	Result	Execution time	Memory
719251		thimote75	Tracks in the Snow (BOI13_tracks)	C++14	47.50 / 100	2131 ms	878076 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

imap positions;
int height, width;

imap visited;
int stage = 1;

bool dfs (int x, int y, int type) {
    if (positions[x][y] == EMPTY) return true;
    if (positions[x][y] != type 
     && visited  [x][y] == EMPTY) return false;

    if (visited[x][y] == stage) return true;
    visited[x][y] = stage;

    bool result = true;
    if (x != 0) result &= dfs(x - 1, y, type);
    if (y != 0) result &= dfs(x, y - 1, type);
    if (x != height - 1) result &= dfs(x + 1, y, type);
    if (y != width  - 1) result &= dfs(x, y + 1, type);

    return result;
}

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;
        }
    }

    int count = 1;
    while (!dfs(0, 0, (positions[0][0] + count + 1) & 1)) {
        count ++;
        stage ++;
    }
    
    cout << count << endl;
}

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