Submission #1270128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270128		JohnnyVenturas	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	886 ms	163724 KiB

tracks

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

/*

Input:

    H : int [1, 4000]
    W : int [1, 4000]


    `map` :

        . -> untouched
        R -> rabit
        F -> fox


    Rules:
        1. Each animal starts at (0,0) moves along xy axes
        2. Each new animal footprint replaces old one



        ........ RRR..... FFR.....
        ........ ..RRR... .FRRR...
        ........ ..R..... .FFFFF..
        ........ ..RRRR.R ..RRRFFR
        ........ .....RRR .....FFF

        RFR.....
        .FRRR...
        .FFFFF..

*/

int rows[] = {-1, 1, 0, 0};
int cols[] = {0, 0, -1, 1};


struct point {
    int r, c, distance;

    point(int r, int c) : r(r), c(c) {}

    point(int r, int c, int distance) : r(r), c(c) , distance(distance) {}
};


void bfs(const vector<string> &tracks) { 

    point start(0,0,0);
    
    deque<point> bfs_queue;


    vector<vector<bool>> visited(tracks.size(), vector(tracks[0].size(), false));


    bfs_queue.push_front(start);

    int max_animals = 0;

    while(!bfs_queue.empty()) {
        point shortest_point_so_far = bfs_queue.front(); 
        bfs_queue.pop_front();

        int r = shortest_point_so_far.r , c = shortest_point_so_far.c, distance = shortest_point_so_far.distance;

        visited[shortest_point_so_far.r][shortest_point_so_far.c] = true;

        max_animals = max(max_animals, distance);

        for(int i = 0 ; i < 4; ++i) {
            int nr = r + rows[i]; 
            int nc = c + cols[i];

            if (nr < 0 || nc  <0 || nr >= tracks.size() || nc >= tracks[0].size()) {
                continue;
            }

            if(tracks[nr][nc] == '.') continue;

            if(visited[nr][nc]) continue;

            if(tracks[nr][nc] != tracks[r][c]) {
                bfs_queue.push_back(point(nr, nc, distance + 1));
            } else {
                bfs_queue.push_front(point(nr, nc, distance));
            }

        }
    }

    cout << max_animals + 1 << "\n";
}

int main() {
    int h, w;
    cin >> h >> w;

    vector<string> tracks(h);       

    for (int i = 0; i < h; ++i) {
        cin >> tracks[i];
    }

    bfs(tracks);
}

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