USACO Silver 2018 February - Snow Boots

Authors: Qi Wang, Ryan Chou, Juheon Rhee

Appears In

Silver - Flood Fill

Explanation

Due to the low bounds on $N$ and $B$ , we can run a DFS (Depth First Search) on every possible location and boot size Farmer John could be wearing.

Implementation

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

C++

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 250;
int n;
int m;

Java

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

public class snowboot {
	static List<Pair<Integer, Integer>> B = new ArrayList<>();
	static int[] D;
	static boolean[][] vist;
	static int N, M, A = 10000;
	public static void main(String[] args) throws IOException {
		InputReader in = new InputReader("snowboots.in");

Python

with open("snowboots.in") as r:
	n, b = map(int, r.readline().split())
	depth = list(map(int, r.readline().split()))
	max_depth = [[*map(int, r.readline().split())] for _ in range(b)]

stor = [[0] * b for _ in range(n)]
stor[0][0] = 1
for i in range(n):
	cur = -1
	for j in range(b):

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!