2017 Feb Silver Problem 3 Why Did the Cow Cross the Road III

Official Problem Statement

Why Did the Cow Cross the Road III

Problem

The problem, "Why Did the Cow Cross the Road III," from the USACO 2017 February Contest, Silver, presents a grid of squares where cows can generally move between adjacent squares unless blocked by roads. The task is to determine how many pairs of cows will be unable to reach the same square given these conditions.

Solution

he solution involves the use of either Breadth-First Search (BFS) or Depth-First Search (DFS) algorithms. By arbitrarily considering a cow, we can perform a BFS or DFS to ascertain which squares the cow can reach. If the cow's square is reachable, we can then determine which cows are unable to meet. To find all pairs of cows, we execute the BFS/DFS for each cow and count the cows that cannot be reached.

Here is an overview of the implemented solution in Java:

• The solution first initializes an array to represent the grid, along with arrays for the x and y coordinates, which will be useful for DFS.

• It then reads input data, where the positions of the roads and cows are specified.

• For each cow, the solution runs a DFS to mark which fields are reachable from the current cow's position.

• It then checks for each previously processed cow if its field is reachable from the current cow's position. If it is not reachable, it increases the answer by one.

• The solution repeats this process for all cows.

This problem showcases the application of BFS/DFS in solving real-life problems using an elegant algorithmic approach.

Code

C++

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

// Define the possible directions to move in the grid
vector<pair<int, int>> directions = {
		make_pair(-1, 0),
		make_pair(1, 0),
		make_pair(0, 1),
		make_pair(0, -1)
	};

// Depth First Search Function
int dfs(vector<vector<int>>& field, map<pair<int, int>, vector<pair<int, int>>>& roadMap, int i, int j) {
	if (i < 0 || j < 0 || i >= field.size() || j >= field[0].size() || field[i][j] < 0) {
		return 0;
	}

	int count = field[i][j];
	field[i][j] = -1;

	pair<int, int> current(i, j);
	vector<pair<int, int>> blockedPaths = roadMap[current];
	
	for (auto direction : directions) {
		pair<int, int> next = make_pair(current.first + direction.first, current.second + direction.second);
		if (find(blockedPaths.begin(), blockedPaths.end(), next) == blockedPaths.end()) {
			count += dfs(field, roadMap, next.first, next.second);
		}
	}

	return count;
}

int main() {
	ifstream fin("countcross.in");
	ofstream fout("countcross.out");

	int gridSize, numCows, numRoads;
	fin >> gridSize >> numCows >> numRoads;

	// Create a map to hold road data
	map<pair<int, int>, vector<pair<int, int>>> roadMap;
	for (int i = 0; i < numRoads; i++) {
		pair<int, int> point1, point2;
		fin >> point1.first >> point1.second >> point2.first >> point2.second;
		point1.first--;
		point1.second--;
		point2.first--;
		point2.second--;
		roadMap[point1].push_back(point2);
		roadMap[point2].push_back(point1);
	}

	// Create a 2D vector to hold field data
	vector<vector<int>> field(gridSize, vector<int>(gridSize, 0));
	for (int i = 0; i < numCows; i++) {
		int x, y;
		fin >> x >> y;
		field[x-1][y-1] = 1;
	}

	// Traverse the field and perform dfs on each section
	vector<int> sections;
	for (int i = 0; i < gridSize; i++) {
		for (int j = 0; j < gridSize; j++) {
			if (field[i][j] > 0) {
				int count = dfs(field, roadMap, i, j);
				if (count > 0) sections.push_back(count);
			}
		}
	}

	// Calculate total inaccessible pairs of cows
	int totalPairs = 0;
	for (int i = 0; i < sections.size(); i++) {
		for (int j = i + 1; j < sections.size(); j++) {
			totalPairs += sections[i] * sections[j];
		}
	}

	// Output the result
	fout << totalPairs << "\n";

	return 0;
}

Java

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

class Pair {
    public int first, second;
    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }

    // Overriding equals() to compare two Pair objects
    @Override
    public boolean equals(Object obj) {
        if(this == obj) {
            return true;
        }

        if(obj == null || obj.getClass()!= this.getClass()) {
            return false;
        }

        Pair pair = (Pair) obj;
        return (pair.first == this.first && pair.second == this.second);
    }
}

public class Main {
    static List<Pair> directions = Arrays.asList(
            new Pair(-1, 0),
            new Pair(1, 0),
            new Pair(0, 1),
            new Pair(0, -1)
    );

    public static int dfs(int[][] field, Map<Pair, List<Pair>> roadMap, int i, int j) {
        if (i < 0 || j < 0 || i >= field.length || j >= field[0].length || field[i][j] < 0) {
            return 0;
        }

        int count = field[i][j];
        field[i][j] = -1;

        Pair current = new Pair(i, j);
        List<Pair> blockedPaths = roadMap.getOrDefault(current, new ArrayList<>());

        for (Pair direction : directions) {
            Pair next = new Pair(current.first + direction.first, current.second + direction.second);
            if (!blockedPaths.contains(next)) {
                count += dfs(field, roadMap, next.first, next.second);
            }
        }

        return count;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader fin = new BufferedReader(new FileReader("countcross.in"));
        PrintWriter fout = new PrintWriter(new BufferedWriter(new FileWriter("countcross.out")));

        StringTokenizer st = new StringTokenizer(fin.readLine());
        int gridSize = Integer.parseInt(st.nextToken());
        int numCows = Integer.parseInt(st.nextToken());
        int numRoads = Integer.parseInt(st.nextToken());

        Map<Pair, List<Pair>> roadMap = new HashMap<>();
        for (int i = 0; i < numRoads; i++) {
            st = new StringTokenizer(fin.readLine());
            Pair point1 = new Pair(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
            Pair point2 = new Pair(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1);
            roadMap.computeIfAbsent(point1, k -> new ArrayList<>()).add(point2);
            roadMap.computeIfAbsent(point2, k -> new ArrayList<>()).add(point1);
        }

        int[][] field = new int[gridSize][gridSize];
        for (int i = 0; i < numCows; i++) {
            st = new StringTokenizer(fin.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;
            field[x][y] = 1;
        }

        List<Integer> sections = new ArrayList<>();
        for (int i = 0; i < gridSize; i++) {
            for (int j = 0; j < gridSize; j++) {
                if (field[i][j] > 0) {
                    int count = dfs(field, roadMap, i, j);
                    if (count > 0) sections.add(count);
                }
            }
        }

        int totalPairs = 0;
        for (int i = 0; i < sections.size(); i++) {
            for (int j = i + 1; j < sections.size(); j++) {
                totalPairs += sections.get(i) * sections.get(j);
            }
        }

        fout.println(totalPairs);
        fout.close();
    }
}

Python

from collections import defaultdict

directions = [
    (-1, 0),
    (1, 0),
    (0, 1),
    (0, -1)
]

def dfs(field, m, i, j):
    if i < 0 or j < 0 or i >= len(field) or j >= len(field):
        return 0
    if field[i][j] < 0:
        return 0

    cnt = field[i][j]
    field[i][j] = -1

    s = (i, j)
    walls = m[s]
    
    for d in directions:
        new_s = (s[0] + d[0], s[1] + d[1])
        if new_s not in walls:
            cnt += dfs(field, m, new_s[0], new_s[1])

    return cnt

with open('countcross.in') as fin:
    n, k, r = map(int, fin.readline().split())

    m = defaultdict(list)
    for _ in range(r):
        p1, p2 = (tuple(map(int, line.split())) for line in fin)
        p1 = (p1[0] - 1, p1[1] - 1)
        p2 = (p2[0] - 1, p2[1] - 1)
        m[p1].append(p2)
        m[p2].append(p1)

    field = [[0]*n for _ in range(n)]

    for _ in range(k):
        a, b = map(int, fin.readline().split())
        field[a-1][b-1] = 1

    sections = []

    for i in range(n):
        for j in range(n):
            if field[i][j] <= 0:
                continue
            cnt = dfs(field, m, i, j)
            if cnt > 0:
                sections.append(cnt)

    total = 0
    for i in range(len(sections)):
        for j in range(i + 1, len(sections)):
            total += sections[i] * sections[j]

    with open('countcross.out', 'w') as fout:
        fout.write(str(total) + "\n")