#K3281. Maximum Treasures
Maximum Treasures
Maximum Treasures
You are given a grid with n rows and m columns. Each cell contains either a treasure represented by T or is empty, represented by .. Two cells are considered connected if they are adjacent horizontally or vertically.
Your task is to determine the maximum number of treasures that can be collected in a single connected component. In other words, find the largest connected group of cells that contain the treasure T.
The connectivity can be formally expressed as: two cells (i, j) and (i', j') are adjacent if and only if |i-i'| + |j-j'| = 1. The answer is the maximum size among all connected sets of cells containing T.
You may assume that the grid dimensions and the number of treasures are such that a recursive depth-first search (DFS) solution will work efficiently.
Note: If there are no treasures (T) in the grid, the answer is 0.
inputFormat
The input is given via standard input (stdin) and has the following format:
n m row_1 row_2 ... row_n
The first line contains two integers n and m, the number of rows and columns respectively. Each of the following n lines contains a string of length m composed of characters 'T' (treasure) and '.' (empty cell).
outputFormat
Output a single integer to standard output (stdout): the maximum number of treasures in a single connected component.
## sample4 4
.T..
.TT.
..T.
TT..
4