Problem Statement
In the year 2020, the COVID-19 pandemic posed a severe challenge globally, including in India. As the virus spread across various cities, public health officials and authorities faced the critical task of managing and containing the outbreak. To effectively allocate resources and implement quarantine measures, they needed to analyze the extent of infection spread within each city.
Imagine you are a public health official tasked with managing the COVID-19 pandemic in Mumbai. You have received a 2D map of the city, but the data collection was not done systematically, so instead of total counts of infected cases in each area, the map includes information on COVID-19 infections in the following format:
- '1' denotes a person with an active COVID-19 virus.
- '0' denotes a person with a negative COVID-19 virus.
Your task is to identify neighbourhoods with the highest COVID-19 virus, where a neighbourhood denotes a cluster of people with an active COVID-19 virus and the connection between these people on the map is either horizontal or vertical.
Identify the neighbourhood with the highest COVID-19 virus and return the population of that neighbourhood.
Input Format
The first line of input contains one integer t, which is the number of test cases.
Each test case has the following input:
- The first line contains two space-separated integers m and n, where m × n denotes the size of the map provided to you, with m denoting the number of rows and n denoting the number of columns.
- The next m lines each have n space-separated integers representing the map of the city.
Constraints
- 1 ≤ t ≤ 100
- 1 ≤ m, n ≤ 100
Output Format
For each test case, print a single integer, denoting the population of the largest neighbourhood.
Sample Input
2
4 5
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
Sample Output
9
4
Explanation
- In the first test case, there is one large cluster (or neighbourhood) of infected individuals. The population of this neighbourhood is 9, so the output is 9.
- In the second test case, there are three neighbourhoods of infected individuals with population sizes of 1, 2, and 4. The largest neighbourhood has a population of 4, so the output is 4.
Solution
from collections import deque
# Breadth First Search (BFS) function to explore the grid
def bfs(grid, i, j, visited):
# Initialize a queue with the starting position (i, j)
queue = deque([(i, j)])
# Mark the starting cell as visited
visited[i][j] = True
# Initialize the count of cells in the current connected component (neighbourhood)
count = 1
# Define possible directions for movement: right, left, down, up
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# Continue exploring until the queue is empty
while queue:
# Pop the front element from the queue (FIFO order)
x, y = queue.popleft()
# Explore all four possible directions from the current cell
for dx, dy in directions:
# Calculate the new coordinates
nx, ny = x + dx, y + dy
# Check if the new position is within the grid bounds,
# if it has not been visited, and if it is part of the neighborhood ('1')
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and not visited[nx][ny] and grid[nx][ny] == '1':
# Add the new position to the queue for further exploration
queue.append((nx, ny))
# Mark this new position as visited
visited[nx][ny] = True
# Increment the count of connected cells
count += 1
# Return the total count of cells in this connected component
return count
# Function to find the largest neighborhood in the grid
def largest_neighbourhood(grid):
# Initialize a variable to store the maximum population found
max_population = 0
# Create a 2D list to track visited cells, initialized to False
visited = [[False] * len(grid[0]) for _ in range(len(grid))]
# Iterate over every cell in the grid
for i in range(len(grid)):
for j in range(len(grid[0])):
# If the cell is part of a neighborhood ('1') and hasn't been visited
if grid[i][j] == '1' and not visited[i][j]:
# Use BFS to find the size of this neighborhood
max_population = max(max_population, bfs(grid, i, j, visited))
# Return the size of the largest neighborhood found
return max_population
# Main function to handle multiple test cases
def main():
t = int(input().strip()) # Read the number of test cases
results = []
# Process each test case
for _ in range(t):
# Read the dimensions of the grid
rows, cols = map(int, input().strip().split())
grid = []
# Read the grid rows
for _ in range(rows):
# Each row is read as a list of strings ('1' or '0')
grid.append(input().strip().split())
# Find the largest neighborhood for this grid and store the result
result = largest_neighbourhood(grid)
results.append(result)
# Output the results for all test cases
for result in results:
print(result)
# Standard Python boilerplate to ensure the main function runs when the script is executed
if __name__ == "__main__":
main()
Sample Solution Provided by Instructor
from collections import defaultdict
# Disjoint Set Union (DSU) or Union-Find class
class DSU:
def __init__(self, n):
# Initialize parent array where each element is its own parent (self-loop)
self.parent = [i for i in range(n)]
# Initialize rank array to keep track of the depth of trees
self.rank = [0] * n
# Find the representative of the set containing 'x' with path compression
def find(self, x):
# If 'x' is not its own parent, recursively find its parent and perform path compression
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
# Union by rank - combine two sets containing 'x' and 'y'
def union(self, x, y):
rootX = self.find(x)
rootY = self.find(y)
# Only union if 'x' and 'y' are in different sets
if rootX != rootY:
# Union by rank: attach smaller tree under the root of the larger tree
if self.rank[rootX] < self.rank[rootY]:
self.parent[rootX] = rootY
elif self.rank[rootX] > self.rank[rootY]:
self.parent[rootY] = rootX
else:
# If ranks are equal, arbitrarily make one the root and increase its rank
self.parent[rootX] = rootY
self.rank[rootY] += 1
if __name__ == '__main__':
t = int(input()) # Number of test cases
for tt in range(t):
m, n = map(int, input().split()) # Dimensions of the grid
covid_map = []
for i in range(m):
covid_map.append(list(map(int, input().split()))) # Read the grid map
# Initialize DSU with 'm * n' elements (one for each cell in the grid)
dsu = DSU(m * n)
# Helper function to convert 2D grid coordinates to 1D DSU index
def index(i, j):
return i * n + j
# Iterate over the grid to union adjacent infected cells (i.e., with value 1)
for i in range(m):
for j in range(n):
if covid_map[i][j] == 1:
# Union with the cell above it if it's also infected
if i > 0 and covid_map[i - 1][j] == 1:
dsu.union(index(i, j), index(i - 1, j))
# Union with the cell to the left if it's also infected
if j > 0 and covid_map[i][j - 1] == 1:
dsu.union(index(i, j), index(i, j - 1))
# Use a dictionary to count the size of each connected component
neighbourhood = defaultdict(int)
for i in range(m):
for j in range(n):
if covid_map[i][j] == 1:
# Find the root of the current infected cell and count it in the neighbourhood
neighbourhood[dsu.find(index(i, j))] += 1
# Determine the size of the largest connected component
highest_population = max(neighbourhood.values(), default=0)
print(highest_population)