IOI 2009 - Mecho

 Problem Link

Time Complexity: O(N²log(N²))

Algorithms used: Binary Search, BFS

An N * N grid is given in which Mecho (a bear) needs to reach his cave before the bees get him. He wants to leave his position at the last possible moment. Mecho can move to the squares above, below, left and right of him, if it is a grassy patch. The bees follow the same rules. The bees spread from square to square, whereas Mecho moves from square to square. Mecho can enter his cave, but the bees cannot.

This problem can be represented as a graph problem, where the squares are nodes in a graph, and edges are drawn between grassy patches. 

Assuming that Mecho can reach his cave before the bees, it is guaranteed that Mecho can do this if he waits for any time between 0 and x. Here, the optimal answer would be x, since he wants to wait at the last possible moment. Any waiting time greater than x would allow the bees to catch Mecho.

From this observation, we find out that we can binary search on the waiting time to find the latest possible leaving time. For a waiting time x, we check if Mecho can reach his cave before the bees. If he can, then binary search on numbers greater than x, otherwise, binary search on numbers left of x. Do this until we are left with a single waiting time.

To see if Mecho can reach his cave before the bees, he needs to have a path on which every square is a grassy patch, and is reachable by Mecho before the bees. 

Run one BFS for the bees, and record the time taken for the bees to reach every possible nodes in the graph. Then run another BFS for Mecho, where a node will only be visited if it is a grassy patch and the bees took more time reach the node than Mecho. If both these conditions are fulfilled, then we can say that Mecho reached the node before the bees. At the end of the BFS, check if Mecho reached any of the four node surrounding his cave. If he did, then Mecho successfully reached the cave when he waited for x time. Otherwise, Mecho will have to wait for less than x time.

Output the maximum waiting time found out by the binary search. If Mecho cannot reach the cave even when he waited for 0 time, then there is no path from his starting position to the cave. In this case, output -1 to indicate this.

Code

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 800;

vector <string> field(MAX_N);

bool bees_visited[MAX_N][MAX_N], mecho_visited[MAX_N][MAX_N];

//mecho_time records the time taken for mecho to reach node[x][y].

//bees_time does the same for the bees

int mecho_time[MAX_N][MAX_N], bees_time[MAX_N][MAX_N];

queue <pair <int, int>> q;

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

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

int n, s;

bool valid_sq(int x, int y){

    if (x >= 0 && x < n && y >= 0 && y < n && (field[x][y] == 'G' || field[x][y] == 'M'))

        return true;

    return false;

}

int main()

{

    cin >> n >> s;

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

        cin >> field[i];

    vector <pair <int, int>> hives;

    int mechox, mechoy, home_x, home_y;

    //find x and y coordinates for for Mecho, the bees and the cave

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

        for (int j = 0; j < n; j++){

            if (field[i][j] == 'M'){

                mechox = i;

                mechoy = j;

            }else if (field[i][j] == 'H'){

                hives.push_back({i, j});

            }else if (field[i][j] == 'D'){

                home_x = i;

                home_y = j;

            }

        }

    }

    //binary search on waiting time

    int l = 0, r = n*n;

    while (l <= r){

        int eating_time = (l + r) / 2;

        memset(bees_visited, false, sizeof(bees_visited));

        memset(mecho_visited, false, sizeof(mecho_visited));

        memset(bees_time, 0, sizeof(bees_time));

        memset(mecho_time, 0, sizeof(mecho_time));

        //move bees

        for (auto i : hives){

            q.push({i.first, i.second});

            bees_visited[i.first][i.second] = true;

        }

        while (!q.empty()){

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

            q.pop();

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

                int nx = x + dx[i], ny = y + dy[i];

                if (valid_sq(nx, ny) && !bees_visited[nx][ny]){

                    bees_time[nx][ny] = bees_time[x][y] + 1;    

                    q.push({nx, ny});

                    bees_visited[nx][ny] = true;

                }

            }

        }

        //move Mecho

        q.push({mechox, mechoy});

        mecho_visited[mechox][mechoy] = true;

        if (bees_time[mechox][mechoy] <= eating_time)

            q.pop();

        while (!q.empty()){

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

            q.pop();

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

                int nx = x + dx[i], ny = y + dy[i];

                //check if mecho reaces node[x][y] before the bees

                /*divide the time mecho takes to reach a node by s, since mecho

                  walks s steps at a time.

                  substract the eating time from the time taken for the bees to

                  reach the node, because that time was used by mecho for eating

                */

                if (valid_sq(nx, ny) && !mecho_visited[nx][ny] &&

                    (mecho_time[x][y] + 1) / s < bees_time[nx][ny] - eating_time){

                    mecho_visited[nx][ny] = true;

                    q.push({nx, ny});

                    mecho_time[nx][ny] = mecho_time[x][y] + 1;

                }

            }

        }

        //check if mecho reached a node surrounding his cave before the bees

        bool mecho_reached = false;

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

            int nx = home_x+ dx[i], ny = home_y + dy[i];

            if (valid_sq(nx, ny) && (mecho_time[nx][ny] / s) < bees_time[nx][ny] - eating_time

                && mecho_visited[nx][ny])

                mecho_reached = true;

        }

        if (mecho_reached)

            l = eating_time + 1;

        else

            r = eating_time - 1;

        }

    cout << l - 1 << '\n';

}