Submission #1265746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265746		chezpotato	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	600 ms	42980 KiB

tracks

#include <bits/stdc++.h>
using namespace std;

int main()
{
    // freopen("input.in", "r", stdin);
    int height, width; cin >> height >> width;
    vector<string> grid(height);
    for(int i=0; i<height; i++) cin >> grid[i];

    int tot = 0;
    char curanimal = grid[0][0];
    vector<vector<bool>> vis(height, vector<bool>(width, false)); vis[0][0] = true;
    queue<pair<int, int>> foxq;
    queue<pair<int, int>> rabbitq;
    if(curanimal == 'F') foxq.push({0,0});
    else rabbitq.push({0,0});

    while(!foxq.empty() || !rabbitq.empty()){
        tot++;
        if(foxq.empty()){
            while(!rabbitq.empty()){
                //working with rabbits
                //flood fill
                auto cur = rabbitq.front(); rabbitq.pop();
                if(cur.first > 0 && !vis[cur.first-1][cur.second]){
                    //flood up
                    if(grid[cur.first-1][cur.second] == 'F') foxq.push({cur.first-1, cur.second});
                    else if(grid[cur.first-1][cur.second] == 'R') rabbitq.push({cur.first-1, cur.second});
                    vis[cur.first-1][cur.second] = true;
                }
                if(cur.first < height-1 && !vis[cur.first+1][cur.second]){
                    //flood down
                    if(grid[cur.first+1][cur.second] == 'F') foxq.push({cur.first+1, cur.second});
                    else if(grid[cur.first+1][cur.second] == 'R') rabbitq.push({cur.first+1, cur.second});
                    vis[cur.first+1][cur.second] = true;
                }
                if(cur.second > 0 && !vis[cur.first][cur.second-1]){
                    //flood left
                    if(grid[cur.first][cur.second-1] == 'F') foxq.push({cur.first, cur.second-1});
                    else if(grid[cur.first][cur.second-1] == 'R') rabbitq.push({cur.first, cur.second-1});
                    vis[cur.first][cur.second-1] = true;
                }
                if(cur.second < width-1 && !vis[cur.first][cur.second+1]){
                    //flood right
                    if(grid[cur.first][cur.second+1] == 'F') foxq.push({cur.first, cur.second+1});
                    else if(grid[cur.first][cur.second+1] == 'R') rabbitq.push({cur.first, cur.second+1});
                    vis[cur.first][cur.second+1] = true;
                }
            }
        }
        else{
            while(!foxq.empty()){
                //working with foxes
                auto cur = foxq.front(); foxq.pop();
                if(cur.first > 0 && !vis[cur.first-1][cur.second]){
                    //flood up
                    if(grid[cur.first-1][cur.second] == 'F') foxq.push({cur.first-1, cur.second});
                    else if(grid[cur.first-1][cur.second] == 'R') rabbitq.push({cur.first-1, cur.second});
                    vis[cur.first-1][cur.second] = true;
                }
                if(cur.first < height-1 && !vis[cur.first+1][cur.second]){
                    //flood down
                    if(grid[cur.first+1][cur.second] == 'F') foxq.push({cur.first+1, cur.second});
                    else if(grid[cur.first+1][cur.second] == 'R') rabbitq.push({cur.first+1, cur.second});
                    vis[cur.first+1][cur.second] = true;
                }
                if(cur.second > 0 && !vis[cur.first][cur.second-1]){
                    //flood left
                    if(grid[cur.first][cur.second-1] == 'F') foxq.push({cur.first, cur.second-1});
                    else if(grid[cur.first][cur.second-1] == 'R') rabbitq.push({cur.first, cur.second-1});
                    vis[cur.first][cur.second-1] = true;
                }
                if(cur.second < width-1 && !vis[cur.first][cur.second+1]){
                    //flood right
                    if(grid[cur.first][cur.second+1] == 'F') foxq.push({cur.first, cur.second+1});
                    else if(grid[cur.first][cur.second+1] == 'R') rabbitq.push({cur.first, cur.second+1});
                    vis[cur.first][cur.second+1] = true;
                }
            }
        }
    }
    cout << tot << endl;
}

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