Contest Python: USACO Bronze › Unit 13 — Grids, Graphs & Traversal
Exercises: Unit 13 — Grids, Graphs & Traversal
Each problem is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper): import sys; data = sys.stdin.read(), parse it, then print. Use from collections import deque for BFS; recursion with a visited set for DFS/flood-fill. Write each program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.
Exercise 1: Friendship Degrees
The first line contains N M A B. The next M lines each contain an undirected friendship edge u v. Build a plain adjacency-list dictionary. Print two integers separated by one space: the degree of A, then the degree of B. The sample makes the final edge touch only B; it must be stored at both endpoints for B's decisive degree to be correct.
Constraints. 2 <= N <= 200000, 1 <= M <= 200000, and 1 <= A, B, u, v <= N.
There are no self-edges or repeated edges, and both queried nodes occur in at least one edge.
Use a plain dictionary with if u not in adj: adj[u] = [], then append each undirected edge to both endpoint lists.
Sample Input
6 5 2 5
1 2
2 3
2 4
4 5
5 6Sample Output
3 2How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 2: Paint One Room
The first line contains R C start_r start_c, followed by R grid rows. An open cell is ., and a wall is #. The start is guaranteed open. Use recursive flood-fill with a visited set passed as an argument. Print the number of open cells in the start's four-neighbour region. Diagonal contact does not connect regions; the isolated final-row cell in the sample is not counted.
Constraints. 1 <= R, C <= 20, R * C <= 400, 0 <= start_r < R, and 0 <= start_c < C.
Each row contains exactly C characters from . and #.
Use recursive four-neighbour flood-fill and pass the mutable visited set to every call.
Sample Input
4 5 0 0
..###
.####
...##
####.Sample Output
6How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 3: Count the Islands
The first line contains R C, followed by a map whose land cells are # and water cells are .. Two land cells belong to the same island only when they share a side. Use recursive flood-fill to print the number of islands. The sample has two side-connected islands plus one land cell that touches another island only diagonally, so that final cell is a separate third island.
Constraints. 1 <= R, C <= 20 and R * C <= 400.
Each row contains exactly C characters from # and ..
Use recursive four-neighbour flood-fill with one visited set passed as an argument.
Sample Input
4 5
##...
#..#.
...##
..#..Sample Output
3How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 4: Fewest Maze Steps
The first line contains R C, followed by a maze. S is the start, T is the target, . is open, and # is a wall. Moving one cell up, down, left, or right costs one step. Use BFS with a FIFO deque, a visited set, and distances to print the fewest steps from S to T. Print -1 if T is unreachable. The sample's target is reached only after the last downward move, so the decisive shortest distance is 8.
Constraints. 1 <= R, C <= 500 and R * C <= 200000.
The grid contains exactly one S and one T, with all other cells . or #.
Use append to enqueue, popleft to dequeue, and while len(queue) > 0.
Sample Input
5 6
S...##
.##...
...#..
##...#
....T#Sample Output
8How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 5: Emergency Exit
The first line contains R C, followed by a building map. S is the start, E is the exit, . is open floor, and # is a wall. Use BFS through four-neighbour open cells. Print YES if the exit is reachable and NO if it is impossible to reach. The sample keeps E visible but completely separated, so the required impossible sentinel is NO.
Constraints. 1 <= R, C <= 500 and R * C <= 200000.
The grid contains exactly one S and one E, with all other cells . or #.
Use a FIFO deque, visited, and four-neighbour movement.
Sample Input
4 5
S...#
#####
...#.
.#..ESample Output
NOHow this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 6: How Far Does the News Spread?
The first line contains N M start. The next M lines each contain an undirected friendship edge u v. Student start learns some news and tells every friend, who tells their friends, and so on. Build a plain adjacency-list dictionary, then use recursive DFS with a visited set passed as an argument. Print how many students hear the news, counting start. The sample contains the cycle 1-2-3-1, so visited must stop DFS from circling forever, and students 6, 7 and 8 form a separate group the news never reaches.
Constraints. 2 <= N <= 400, 1 <= M <= 2000, and 1 <= start, u, v <= N.
There are no self-edges or repeated edges. A student who appears in no edge has no friends.
Use recursive DFS; pass and mutate visited, and store every undirected edge at both endpoints.
Sample Input
8 7 2
1 2
2 3
3 1
3 4
4 5
6 7
7 8Sample Output
5How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 7: Separate Networks
The first line contains N M start target. The next M lines contain undirected edges. Use recursive DFS on an adjacency-list dictionary and print YES if target is reachable from start, or NO if it is unreachable. The sample includes a cycle in the start's component, but the decisive final edge belongs to a separate component, so the answer is NO.
Constraints. 2 <= N <= 400, 1 <= M <= 2000, and 1 <= start, target, u, v <= N.
There are no self-edges or repeated edges.
Use recursive DFS with visited passed as an argument; store every undirected edge at both endpoints.
Sample Input
7 6 1 7
1 2
2 3
3 1
3 4
5 6
6 7Sample Output
NOHow this is checked: Checked by running your program on 3 test inputs (1 sample, 2 hidden) and comparing its output word by word.
Exercise 8: Largest Meadow
The first line contains R C, followed by a map whose meadow cells are . and rocks are #. A meadow is a four-neighbour connected region of open cells. Use recursive flood-fill to print the size of the largest meadow, or 0 if there are no open cells. The sample contains several disjoint meadows; the winding left meadow is largest, and its decisive final cell raises its size to 7.
Constraints. 1 <= R, C <= 20 and R * C <= 400.
Each row contains exactly C characters from . and #.
Use recursive four-neighbour flood-fill and pass the shared visited set as an argument.
Sample Input
5 6
..#...
.##.##
...#..
##.#..
#####.Sample Output
7How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 9: Farthest Delivery
The first line contains N M start. The next M lines contain undirected roads. Every node is reachable from start. Build an adjacency-list dictionary and use BFS distances to print the greatest shortest-path distance from start to any node. The final road in the sample extends the only farthest route, making the decisive answer 5. If the reachability guarantee were removed, an unreachable node's distance would use sentinel -1; this problem guarantees that sentinel is never needed.
Constraints. 2 <= N <= 200000, 1 <= M <= 200000, and 1 <= start, u, v <= N.
There are no self-edges or repeated edges, and every node is reachable from start.
Use a FIFO deque, while len(queue) > 0, a visited set, and a distance dictionary.
Sample Input
7 7 1
1 2
1 3
2 4
3 4
4 5
5 6
6 7Sample Output
5How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.