Taco - Maximum Fruit Points Path

You are given a rectangular grid of dimensions \(n\) \(\times\) \(m\). Each cell in the grid contains one of the following characters:

• 'X': Represents a rock. You cannot pass through these cells.
• 'F': Represents a cell with fruit, which gives you 1 point when visited.
• '.': Represents an empty cell where you can move.

You start at the top-left corner (cell \((0,0)\)) and your goal is to reach the bottom-right corner (cell \((n-1, m-1)\)). From any cell, you may only move either right or down. If the start or the destination cell is a rock, then reaching the destination is impossible.

Your task is to determine the maximum number of fruit points you can collect on your path from the start to the destination. If there is no valid path, print \(-1\).

The recurrence relation for the dynamic programming solution is given by:

$$dp[i][j]=\begin{cases} \max(dp[i-1][j],\,dp[i][j-1])+\mathbb{1}_{\{grid[i][j]=='F'\}} & \text{if grid}[i][j] \neq 'X' \\ -1 & \text{if cell is blocked or unreachable} \end{cases}$$

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n, m \leq 1000)\) representing the number of rows and columns respectively.

The following \(n\) lines each contain a string of length \(m\) consisting of the characters 'X', 'F', and '.', representing the grid.

Input is read from standard input (stdin).

outputFormat

Output a single integer: the maximum number of fruit points that can be collected on the path from the top-left to the bottom-right corner. If no such path exists, output \(-1\).

Output is written to standard output (stdout).

## sample

4 5
F...X
...XF
..F..
...FF

4