USACO 2019 January Contest Silver Division - Icy Perimeter

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We will use floodfill to compute a temporary area and perimeter for the given component and then we compare them with the best such areas/perimeters we found so far. One has to pay attention to the way we compute the area and the perimeter as for a given square, in order to increase the perimeter, we have to add up 1 for each side that is adjacent to a square not in the component.

Source code

The source code in C++ can be seen below.

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

const int MAXN = 1e3 + 5;

char mat[MAXN][MAXN];
bool visited[MAXN][MAXN];

int dx[4] = {-1, 0, 1, 0};  // Directions
int dy[4] = {0, 1, 0, -1};

long long perim = 0, ar = 0, perimeter = 0, area = 0;

// floodfill (Lee Algorithm)
void lee(int a, int b, int n) {
    queue<pair<int, int>> q;
    q.push({a, b});
    visited[a][b] = 1;

    while (!q.empty()) {
        int val1 = q.front().first, val2 = q.front().second;
        q.pop();

        for (int dir = 0; dir < 4; dir++) {
            int newX = val1 + dx[dir];  // New coords
            int newY = val2 + dy[dir];

            if (newX < 0 || newX >= n || newY < 0 || newY >= n) {  // If it's not in the matrix
                perim++;
                continue;
            }
            if (visited[newX][newY]) {  // If it was already visited
                continue;
            }
            if (mat[newX][newY] == '.') {  // If it's a '.' (empty space) update the temporary perimeter
                perim++;
                continue;
            }
            if (mat[newX][newY] == '#') {  // If it's a cell of ice cream, update area.
                ar++;
            }

            visited[newX][newY] = 1;  // Mark as visited
            q.push({newX, newY});     // Push new values
        }
    }
}

int main() {
    freopen("perimeter.in", "r", stdin);
    freopen("perimeter.out", "w", stdout);

    int n, lin, col;

    cin >> n;
    for (lin = 0; lin < n; lin++) {
        for (col = 0; col < n; col++) {
            cin >> mat[lin][col];
        }
    }
    for (lin = 0; lin < n; lin++) {
        for (col = 0; col < n; col++) {
            if (!visited[lin][col] &&
                mat[lin][col] == '#') {  // If we haven't visited it yet and it's an ice cream cell
                lee(lin, col, n);        // Calculate using Lee Algorithm the new area and perimeter
                ++ar;
                if (area == ar) {   // if our current area and the new one are equal
                    perimeter = min(perimeter, perim);  // just consider the smaller perimeter
                } else if (ar > area) { // if our new area is bigger
                    perimeter = perim;  // update both values to the newly calculated ones
                    area = ar;
                }
                perim = ar = 0;  // reset new area and perimeter to 0
            }
        }
    }
    cout << area << " " << perimeter;  // output the values
    return 0;
}