Submission #1049421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049421		DeathIsAwe	Tracks in the Snow (BOI13_tracks)	C++14	19.79 / 100	814 ms	160752 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
char grid[5000][5000];
int visited[5000][5000];
vector<pair<int,int>> foxtrack, rabtrack;


void floodfill(vector<pair<int,int>> &track, int h, int w) {
    pair<int,int> block;
    while (track.size() > 0) {
        block = track[track.size() - 1]; track.pop_back();
        visited[block.first][block.second] = true;
        //cout << block.first << ' ' << block.second << '\n';
        if (block.first > 0) {
            if (!visited[block.first - 1][block.second]) {
                if (grid[block.first - 1][block.second] == 'F') {
                    foxtrack.push_back(make_pair(block.first - 1, block.second));
                } else if (grid[block.first - 1][block.second] == 'R') {
                    rabtrack.push_back(make_pair(block.first - 1, block.second));
                }
            }
        }
        if (block.first < h - 1) {
            if (!visited[block.first + 1][block.second]) {
                if (grid[block.first + 1][block.second] == 'F') {
                    foxtrack.push_back(make_pair(block.first + 1, block.second));
                } else if (grid[block.first + 1][block.second] == 'G') {
                    rabtrack.push_back(make_pair(block.first + 1, block.second));
                }
            }
        }
        if (block.second > 0) {
            if (!visited[block.first][block.second - 1]) {
                if (grid[block.first][block.second - 1] == 'F') {
                    foxtrack.push_back(make_pair(block.first, block.second - 1));
                } else if (grid[block.first][block.second - 1] == 'R') {
                    rabtrack.push_back(make_pair(block.first, block.second - 1));
                }
            }
        }
        if (block.second < w - 1) {
            if (!visited[block.first][block.second + 1]) {
                if (grid[block.first][block.second + 1] == 'F') {
                    foxtrack.push_back(make_pair(block.first, block.second + 1));
                } else if (grid[block.first][block.second + 1] == 'R') {
                    rabtrack.push_back(make_pair(block.first, block.second + 1));
                }
            }
        }
    }
}


int main() {
    int h, w; cin >> h >> w;
    for (int i=0;i<h;i++) {
        for (int j=0;j<w;j++) {
            cin >> grid[i][j];
            visited[i][j] = false;
        }
    }

    char animal = grid[0][0];
    int ans = 0;    
    pair<int,int> block;
    if (grid[0][0] == 'F') {
        foxtrack.push_back(make_pair(0, 0));
    } else {
        rabtrack.push_back(make_pair(0, 0));
    }
    while (true) {
        if (animal == 'F') {
            if (foxtrack.size() == 0) {
                break;
            }
            floodfill(foxtrack, h, w);
            animal = 'R';
        } else {
            if (rabtrack.size() == 0) {
                break;
            }
            floodfill(rabtrack, h, w);
            animal = 'F';
        }
        ans++;
    }
    cout << ans;
}

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