Minimum Additional Farmers

You are given a farm represented as an \(N \times M\) grid. Each cell is either empty, denoted by ., or occupied by a farmer, denoted by F. A farmer can receive water from another farmer if there is at least one adjacent cell (one of the eight directions: \((-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)\)) containing a farmer.

Your task is to determine the minimum number of additional farmers to add (in the empty cells) such that every farmer (both original and added) can receive water from at least one other farmer.

Note: An adjacent cell is one that touches the current cell, including diagonally adjacent cells.

inputFormat

The input is provided via standard input (stdin). The first line contains two integers \(N\) and \(M\), representing the number of rows and columns of the grid, respectively. The following \(N\) lines each contain a string of length \(M\) consisting only of the characters F (farmer) and . (empty cell).

outputFormat

Output the minimum number of additional farmers required so that every farmer in the grid has at least one adjacent farmer. The output should be printed to standard output (stdout) as a single integer.

3 3
F.F
...
.F.

2