USACO Silver 2019 January - Icy Perimeter

Authors: Tanish Tyagi, Brad Ma, Juheon Rhee, David Guo

Edit This Page

Table of Contents

ExplanationImplementation

Official Analysis (C++)

Explanation

We can use BFS to explore each blob, starting from an unvisited #. During BFS, we can calculate the blob’s area by counting the number of # visited and determine its perimeter by analyzing the surroundings of each #.

The perimeter is determined by summing the number of sides of all cells that are either adjacent to a # or are on the boundary.

As we traverse the grid, we can initiate a BFS for each unvisited # to compute the area and perimeter of all blobs. Within the BFS, for each #, we start by assuming that all four of its sides contribute to the perimeter. We then reduce this count by one for each neighboring #, since shared edges do not add to the perimeter.

Implementation

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

C++

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


// Movement directions (up, down, left, right)
const vector<pair<int, int>> DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


pair<int, int> bfs(int row, int col, const vector<vector<char>> &grid,
                   vector<vector<bool>> &visited) {
	const int n = grid.size();  // shorthand

Java

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


public class IcyPerimeter {
	// Movement directions (up, down, left, right)
	private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


	private static int[] bfs(int row, int col, char[][] grid, boolean[][] visited) {
		// Shorthand for the size of the grid
		final int n = grid.length;

Python

from collections import deque
from typing import List, Tuple


# Movement directions (up, down, left, right)
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]




def bfs(
	row: int, col: int, grid: List[str], visited: List[List[bool]]
) -> Tuple[int, int]:

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!

Join Forum