BOI 2013 - Tracks in the Snow

 Problem Link

Tags: BOI, graph, 01 BFS, shortest paths
Time Complexity: O(HW)

This problem uses 0-1 BFS. This is from where I learnt 0-1 BFS.

In this problem, a grid is given which consists of  . (empty square), R (rabbit) and F (foxes). Given the the grid and its dimensions, we are asked to find out the minimum number of animals that could have been present on the grid in total.

(Tricky Test Case - the answer is 3 - minimum of two foxes and one rabbit)

Original	Fox 1	Rabbit 1	Fox 2 - (back to original)

This problem is a graph problem, because every square can be considered as a node, and an edge can be drawn between any two adjacent nodes.

There are 3 options for every pair of adjacent nodes:

1. If either of the 2 nodes were not visited by any animal, then that node(s) should not be included in the node. So, no edge should be drawn here.
2. If the 2 nodes were last visited by the same animal, then the edge weight between the nodes should be 0;edge-weight of 0 means that the same animal could have visited the 2 nodes.
3. If the 2 nodes were last visited by different animals, then the edge between the nodes should be 1; edge-weight of 1 means that two different animals must have visited the 2 nodes.

We need to find the smallest number of animals that could have covered all nodes (henceforth, a node means a square last visited by a fox or a rabbit). But, all nodes may not have been covered by the same animal. Hence, it is necessary to know the number of times a different animal left tracks.

As per the edge-weight logic described above, nodes on the end of an edge with weight 1 indicate that the nodes were last visited by two distinct animals. Simply counting the number of edges with weight 1 would not give the answer, since the same animal could have traversed the nodes on the ends of multiple edges with weight 1.

Instead, we find the shortest path from the starting node(top left node) to every node in the graph, because that would give us the most number of nodes one animal could have traversed, before we need to introduce a new animal to complete the path. 

To do this, the first thought would be to run Dijkstra's algorithm on this weighted graph, but this would exceed time limit because of the priority queue/set. 0-1 BFS is faster, and achieves the same result, since 0-1 BFS would find the shortest path from starting node to every node, while optimally traversing the graph as per the edge weights.

Once the shortest path to all nodes has been found, take the longest of all of them. This is because the longest path indicates the number of animals needed to visited the farthest node in the graph. Then, add 1 to the length of the longest path, since at least one animal must be present on the graph.

Code:

#include <bits/stdc++.h>

using namespace std;

const int MAX_H = 4000;

const int MAX_W = 4000;

vector <string> meadow(MAX_H);

int dis[MAX_H][MAX_W];

bool visited[MAX_H][MAX_W];

int dx[] = {-1, 1, 0, 0};

int dy[] = {0, 0, -1, 1};

bool diff_animal(int x, int y, int diffx, int diffy){

    if (meadow[x][y] != meadow[x + diffx][y + diffy])

        return true;

    return false;

}

bool valid_sq(int x, int y, int h, int w){

    if (x >= 0 && x < h && y >= 0 && y < w && meadow[x][y] != '.')

        return true;

    return false;

}

int main()

{

    int h, w;

    cin >> h >> w;

    for (int i = 0; i < h; i++)

        cin >> meadow[i];

    deque <pair <int, int>> q;

    memset(dis, -1, sizeof(dis));

    int ans = 0;

    dis[0][0] = 0;

    q.push_back({0, 0});

    while (!q.empty()){

        int x = q.front().first, y = q.front().second;

        q.pop_front();

        ans = max(ans, dis[x][y]);

        for (int i = 0; i < 4; i++){

            int curr_x = x + dx[i], curr_y = y + dy[i];

            if (valid_sq(curr_x, curr_y, h, w) && dis[curr_x][curr_y] == -1){

                int d = diff_animal(x, y, dx[i], dy[i]);

                dis[curr_x][curr_y] = dis[x][y] + d;

                if (d == 0)

                    q.push_front({curr_x, curr_y});

                else

                    q.push_back({curr_x, curr_y});

            }

        }

    }

    cout << ans + 1 << '\n';

}

C++ specific: 

Running Dijkstra's algorithm with a priority queue will exceed time limit (time complexity will be (hw)log(hw)). So, run BFS and use a deque and add edges with weight 1 to the back to the queue and edges with weight 0 to the front of the queue.