USACO 2019 US Open Contest Bronze Division - Bucket Brigade

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Standard flood fill, recursion or casework work for this problem.

Source codes

The source codes in C++ and Python can be seen below.

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

int main() 
{
    ifstream cin("buckets.in");
    ofstream cout("buckets.out");

    char grid[12][12];
    int dist[12][12];
    int barnx = 0, barny = 0;
    int lakex = 0, lakey = 0;
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < 10; j++)
        {
            cin >> grid[i][j];
            dist[i][j] = (1<<20);
            if(grid[i][j] == 'B')
                barnx = i, barny = j;
            if(grid[i][j] == 'L')
                lakex = i, lakey = j;
        }

    int ox[] = {0, 1, 0, -1};
    int oy[] = {1, 0, -1, 0};

    queue<pair<int, int> > q;
    q.push({barnx, barny});
    dist[barnx][barny] = 0;

    while(!q.empty())
    {
        pair<int, int> node = q.front();
        q.pop();

        for(int i = 0; i <= 3; i++)
        {
            int nxtx = node.first + ox[i];
            int nxty = node.second + oy[i];
            if(nxtx >= 0 && nxtx <= 9 && nxty >= 0 && nxty <= 9)
            {
                if(grid[nxtx][nxty] == 'R')
                    continue;
                if(dist[nxtx][nxty] == (1<<20))
                {
                    dist[nxtx][nxty] = dist[node.first][node.second] + 1;
                    q.push({nxtx, nxty});
                }
            }
        }
    }
    cout << dist[lakex][lakey] - 1 << '\n';
    return 0;
}

from collections import deque

with open("buckets.in", "r") as fin:
    grid = [list(fin.readline().strip()) for _ in range(10)]
dist = [[1 << 20 for _ in range(10)] for _ in range(10)]
barnx = barny = lakex = lakey = 0
for i in range(10):
    for j in range(10):
        if grid[i][j] == 'B':
            barnx, barny = i, j
        if grid[i][j] == 'L':
            lakex, lakey = i, j
ox = [0, 1, 0, -1]
oy = [1, 0, -1, 0]
q = deque()
q.append((barnx, barny))
dist[barnx][barny] = 0
while q:
    node = q.popleft()
    for i in range(4):
        nxtx = node[0] + ox[i]
        nxty = node[1] + oy[i]
        if 0 <= nxtx < 10 and 0 <= nxty < 10:
            if grid[nxtx][nxty] == 'R':
                continue
            if dist[nxtx][nxty] == (1 << 20):
                dist[nxtx][nxty] = dist[node[0]][node[1]] + 1
                q.append((nxtx, nxty))
with open("buckets.out", "w") as fout:
    fout.write(str(dist[lakex][lakey] - 1) + "\n")