Problem Statement
You are teaching a class of n students. Each student may be friends with some other students or may have no friends. Students who are friends with each other sit adjacent to each other in the class. If a student a is friends with a student b, but not with a student c, but b is friends with c, then they still sit together as both a and c will sit adjacent to b, their mutual friend. All friendships are symmetric, meaning that if a is a friend of b, then b is a friend of a for all a, b ∈ Students.
You are trying to give the students a group project, but the students are adamant and will not agree to random grouping. You are thus left with no choice but to let them create groups with their friends. This may lead to unequal size groups.
You don't know which student is friends with which student, and asking the same from all n students will require a lot of time. Thus, you decide to simply look at how they are sitting and form groups that way.
A student a will be in the same project group with a student b if either a and b are friends, or a and c are friends and b and c are friends, for any arbitrary student c, such that c ≠ a and c ≠ b. Two students are friends with each other if they are sitting adjacent (horizontally or vertically, but not diagonally) to each other.
Given the sitting arrangement of the students in a rectangular classroom, output the number of groups they will form for the project.
Input Format
The first line of input contains a single integer t, which is the number of test cases.
Each test case contains several lines of input:
- The first line of input for each test case contains two space-separated integers n and m, which represent the dimensions of the room.
- The next n lines each contain m space-separated bits, where 0 represents no student is sitting there, and 1 represents a student is sitting there.
Constraints
- 1 ≤ t ≤ 102
- 1 ≤ n, m ≤ 102
- Bij ∈ {0, 1}
Output Format
For each test case, output a single integer x, which is the number of groups the students will form.
Sample Input
1
4 4
1 0 0 1
0 1 1 0
1 0 0 0
1 1 1 1
Sample Output
4
Explanation
In the classroom, there are 4 connected groups of students with sizes {1, 1, 2, 5} sitting together. Thus, they will form 4 groups for the group project.
Solution
def dfs(grid, visited, i, j, n, m):
# Check if the current cell is out of bounds or has been visited already,
# or if the cell is not a student (represented by 1 in the grid).
if i < 0 or j < 0 or i >= n or j >= m or visited[i][j] or grid[i][j] == 0:
return # If any of these conditions are met, return and do not proceed further.
# Mark the current cell as visited
visited[i][j] = True
# Recursively explore all four possible directions: up, down, left, right
# Move up (row - 1)
dfs(grid, visited, i - 1, j, n, m)
# Move down (row + 1)
dfs(grid, visited, i + 1, j, n, m)
# Move left (column - 1)
dfs(grid, visited, i, j - 1, n, m)
# Move right (column + 1)
dfs(grid, visited, i, j + 1, n, m)
def count_groups(grid, n, m):
# Initialize a 2D list `visited` to keep track of which cells have been visited.
# Initially, all cells are unvisited, so all values are set to False.
visited = [[False for _ in range(m)] for _ in range(n)]
# Variable to keep count of the number of groups (connected components)
group_count = 0
# Iterate over every cell in the grid
for i in range(n):
for j in range(m):
# If the current cell contains a student (1) and hasn't been visited yet,
# it's the start of a new group.
if grid[i][j] == 1 and not visited[i][j]:
# Perform DFS to visit all connected cells (part of the same group)
dfs(grid, visited, i, j, n, m)
# Increment the group count after finishing the DFS, indicating one complete group has been found
group_count += 1
# Return the total number of groups found in the grid
return group_count
# Reading input
t = int(input()) # Read the number of test cases
for _ in range(t):
n, m = map(int, input().split()) # Read the dimensions of the grid (n: rows, m: columns)
# Initialize the grid as an empty list
grid = []
# Read each row of the grid
for _ in range(n):
# Convert each input line to a list of integers and append it to the grid
grid.append(list(map(int, input().split())))
# Output the number of groups (connected components of students) for each test case
print(count_groups(grid, n, m))
Sample Solution Provided by Instructor
def groups(grid):
if not grid:
return 0 # If the grid is empty, return 0 as there are no groups.
# Helper function to perform DFS and mark visited cells.
def dfs(i, j):
# If the current cell is out of bounds or not a '1', return (stop recursion).
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != 1:
return
grid[i][j] = 0 # Mark the cell as visited by setting it to '0'.
# Recursively visit all adjacent cells (up, down, left, right).
dfs(i+1, j) # Move down
dfs(i-1, j) # Move up
dfs(i, j+1) # Move right
dfs(i, j-1) # Move left
ngroups = 0 # Initialize the group counter.
# Iterate over all cells in the grid.
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1: # Found an unvisited '1', which is the start of a new group.
ngroups += 1 # Increment the group counter.
dfs(i, j) # Perform DFS to visit the entire group.
return ngroups # Return the total number of groups found.
# Main logic to handle multiple test cases.
t = int(input()) # Read the number of test cases.
for _ in range(t):
n, m = list(map(int, input().split())) # Read the dimensions of the grid.
grid = []
for _ in range(n):
grid.append(list(map(int, input().split()))) # Read the grid row by row.
print(groups(grid)) # Print the number of groups for the current grid.