USACO Silver 2013 Open - What's Up With Gravity

Official Analysis (C++)

Explanation

Since this problem can be reduced to a shortest path problem with edge lengths of 0 or 1, we can use BFS. A transition edge has the weight 1 if the gravity is flipped or 0 if Captain Bovidian only moves left or right. We firstly add all reachable blocks from left and right to the queue. Each element in the queue is a 4-tuple containing the row and column of the block, the number of flips needed to reach it, and the direction of gravity. Then, for each block in the queue, we change the gravity and perform another search for the left and right, eventually adding new blocks to the end of the queue. This way, we will always check blocks that require fewer flips before moving forward.

During the search process, we store the number of flips needed to get to a certain block. We only visit blocks that are not visited yet.

Time Complexity: $\mathcal{O}(N^2)$

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

/**
 * With the given direction of gravity, calculate the row on which captain
 * will fall on.
 * @param direc Direction of the gravity, either 1 or -1
 */
int fall_to_row(int r, int c, int direc, const vector<vector<char>> &grid) {
	while (grid[r][c] == '.' || grid[r][c] == 'C' || grid[r][c] == 'D') {