Editing 2019 Dec Gold Problem 3 Moortal Cowmbat

== Official Problem Statement ==

[http://www.usaco.org/index.php?page=viewproblem2&cpid=971 Moortal Cowmbat]

Problem Statement:

Moortal Cowmbat is a game played on a rectangular grid of size N × M. Each cell of the grid is either empty or contains a single cow. The goal of the game is to move the cows from their initial positions to their final positions.

Solution:

The solution is to use a Breadth-First Search (BFS) algorithm to find the shortest path from the initial position of each cow to its final position. The algorithm works as follows:

1. Start at the initial position of the cow.
2. Check all adjacent cells to see if they are empty.
3. If an empty cell is found, add it to a queue.
4. Repeat steps 2 and 3 until the final position of the cow is reached.

The following C++ code implements the BFS algorithm:

<pre>
#include <queue>
#include <vector>

struct Point {
    int x, y;
};

// Returns the shortest path from start to end
std::vector<Point> bfs(Point start, Point end, int n, int m) {
    std::queue<Point> q;
    q.push(start);
    std::vector<std::vector<bool>> visited(n, std::vector<bool>(m, false));
    visited[start.x][start.y] = true;
    std::vector<Point> path;
    while (!q.empty()) {
        Point curr = q.front();
        q.pop();
        path.push_back(curr);
        if (curr == end) {
            break;
        }
        // Check all adjacent cells
        for (int i = -1; i <= 1; i++) {
            for (int j = -1; j <= 1; j++) {
                int x = curr.x + i;
                int y = curr.y + j;
                if (x >= 0 && x < n && y >= 0 && y < m && !visited[x][y]) {
                    Point next = {x, y};
                    q.push(next);
                    visited[x][y] = true;
                }
            }
        }
    }
    return path;
}
</pre>

[[Category:Yearly_2019_2020]]
[[Category:Gold]]
[[Category:Dynamic Programming]]
[[Category:Floyd-Warshall Algorithm]]
[[Category:Graph]]