USACO Gold 2017 December - Why Did the Cow Cross the Road

Official Analysis

Solution

Instead of treating this as a grid problem, let us try to approach it as a graph problem with nodes and edges.

We first observe that the two intermediary tiles Bessie used to travel do not actually matter because Bessie only feasts on grass tiles every 3 moves and the time to travel between adjacent tiles is a constant $T$. So we want to form a direct edge between each tile that is exactly 3 manhattan distances apart, with a weight of

$\{\text{The time to feast the target grass tile}\} + 3 * T$

However, if the tile Bessie just feasted on is less than 3 units (using manhattan distance) away from Farmer John's tile, then it would be more desirable for Bessie to travel to Farmer John directly than take another 3-distanced tile. So, we also form a direct edge between those two tiles with a weight of

$\{\text{The manhattan distance}\} * T$

Implementation

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define ss second

// Possible directions Bessie can go to eat grass
int dx[] = {1, 0, -1, 0, 3, 0, -3, 0, 2, 2, 1, 1, -1, -1, -2, -2};
int dy[] = {0, 1, 0, -1, 0, 3, 0, -3, 1, -1, 2, -2, 2, -2, 1, -1};

Copy
import java.io.*;
import java.util.*;

public class VisitFJ {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("visitfj");

		// Possible paths cow can take
		int[] dx = {0, 1, 2, 3, 0, 1, 2, -1, -2, -3, -1, -2, 1, -1, 0, 0};
		int[] dy = {3, 2, 1, 0, -3, -2, -1, 2, 1, 0, -2, -1, 0, 0, 1, -1};