Largest Contiguous Exploration Area

Waldo is exploring a city represented as a grid. The grid consists of walls ('#'), roads ('.') and a starting position marked with 'W'. Waldo can move horizontally or vertically (i.e., up, down, left, or right) from his starting position. Once he starts, he can only move on cells with a road ('.'). The starting cell is counted as part of the area even if it is marked with 'W'.

Your task is to calculate the size of the largest contiguous area that Waldo can explore. Formally, if we denote the grid as an N × M matrix and the starting position is given by \( (i,j) \), then the contiguous area \( A \) is defined by the number of cells that can be reached from \( (i,j) \) (including the starting cell) by repeatedly moving to adjacent cells that contain a road. Moves are only allowed in four directions: up, down, left, and right.

Mathematically, if we let the grid be \( G \) and define a move from \( (x,y) \) to \( (x',y') \) as valid if \( |x-x'| + |y-y'| = 1 \) and \( G[x'][y'] = '.' \), then the answer is the number of unique cells in the connected component containing the cell where \( G[x][y] = 'W' \). If there is no starting position present, then the answer is 0.

inputFormat

The input is given via standard input (stdin) and has the following format:

N M
row1
row2
...
rowN

Where:

• N is the number of rows in the grid.
• M is the number of columns in the grid.
• Each of the next N lines represents a row of the grid, consisting of the characters '#' (wall), '.' (road) and 'W' (starting position).

outputFormat

The output should be written to standard output (stdout) — a single integer representing the number of cells in the largest contiguous area Waldo can explore, including the starting cell.

4 5
###..
..#..
.W#..
###..

4