USACO Silver 2017 December - Why Did the Cow Cross the Road III

C++

Note that using set here instead of unordered_set adds an extra $\log R$ factor to the time complexity.

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

struct Road {
	int sr, sc;
	int er, ec;
};

/** to use the struct in a set, a comparator must be implemented. */
inline bool operator<(const Road &r1, const Road &r2) {

Java

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

public class CountCross {
 	Code Snippet: Road Class (Click to expand)

	private static int sideLen;
	private static Set<Road> roads = new HashSet<>();
	private static boolean[][] hasCow;
	private static boolean[][] visited;

Python

Copy
from typing import List, Tuple


def neighbors(r: int, c: int) -> List[Tuple[int, int]]:
	""":return: the 4 cardinal neighbors of a position"""
	return [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]


with open("countcross.in") as read:
	side_len, cow_num, road_num = [int(i) for i in read.readline().split()]