#K3281. Maximum Treasures

    ID: 24948 Type: Default 1000ms 256MiB

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.

## sample
4 4
.T..
.TT.
..T.
TT..
4