#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <vector> // Ensure vector is included
using namespace std;
int H, W; // Height and Width of the meadow grid
vector<string> meadow; // Stores the map of the meadow
// Use vector<vector<bool>> for visited array to handle large dimensions dynamically
// Declared globally to avoid passing large structures repeatedly or stack overflow issues with large grids
vector<vector<bool>> visited;
// Function to check if coordinates (r, c) are within the grid bounds
bool is_valid(int r, int c) {
return r >= 0 && r < H && c >= 0 && c < W;
}
// Function to check if a path exists from the top-left cell (0,0)
// to the bottom-right cell (H-1, W-1) using only cells of the specified 'type' ('R' or 'F').
// Uses Breadth-First Search (BFS).
bool check_path(char type) {
// The path must start at cell (0,0).
// Check if the starting cell (0,0) has the required track type.
if (meadow[0][0] != type) {
// If the starting cell isn't the required type, no path consisting solely of this type can start from (0,0).
return false;
}
// Initialize BFS queue. Stores pairs of {row, column}.
queue<pair<int, int>> q;
// Reset visited array for this specific path check.
// `assign` resizes the outer vector to H elements, each being a vector<bool> of size W initialized to false.
// This is efficient and ensures clean state for each BFS run.
visited.assign(H, vector<bool>(W, false));
// Start BFS from the top-left cell (0,0)
q.push({0, 0});
visited[0][0] = true; // Mark the starting cell as visited
// Define movement directions: Up, Down, Left, Right
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
// Continue BFS as long as there are cells in the queue to explore
while (!q.empty()) {
// Get the current cell from the front of the queue
pair<int, int> curr = q.front();
q.pop(); // Remove the current cell from the queue
int r = curr.first; // Current row
int c = curr.second; // Current column
// Check if we reached the destination cell (H-1, W-1)
if (r == H - 1 && c == W - 1) {
return true; // Path found
}
// Explore adjacent cells (neighbors)
for (int i = 0; i < 4; ++i) {
int nr = r + dr[i]; // Neighbor row
int nc = c + dc[i]; // Neighbor column
// Check if the neighbor cell is valid:
// 1. Within grid bounds (is_valid)
// 2. Contains the required track type (meadow[nr][nc] == type)
// 3. Has not been visited yet in this BFS run (!visited[nr][nc])
if (is_valid(nr, nc) && meadow[nr][nc] == type && !visited[nr][nc]) {
visited[nr][nc] = true; // Mark the neighbor as visited
q.push({nr, nc}); // Add the neighbor to the queue for further exploration
}
}
}
// If the queue becomes empty and the destination was not reached, then no path exists.
return false;
}
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read grid dimensions H (height) and W (width)
cin >> H >> W;
// Read the meadow map into the vector of strings
meadow.resize(H);
bool has_R = false; // Flag to track if any 'R' tracks exist
bool has_F = false; // Flag to track if any 'F' tracks exist
for (int i = 0; i < H; ++i) {
cin >> meadow[i];
// Check for the presence of 'R' and 'F' tracks while reading
// Optimization: stop checking row characters once both types are found
if (!has_R || !has_F) {
for (char c : meadow[i]) {
if (c == 'R') has_R = true;
if (c == 'F') has_F = true;
// If both types found, no need to check further in this row or subsequent rows
if (has_R && has_F) break;
}
}
}
// The problem guarantees at least one track exists on the meadow.
// Case 1: Only Rabbit ('R') tracks exist
if (has_R && !has_F) {
// The problem implies a solution always exists. If only R tracks are present,
// it must be possible to explain the tracks with N=1 animal (a rabbit).
// We technically don't need to call check_path('R') because existence is guaranteed by the problem statement.
cout << 1 << endl;
}
// Case 2: Only Fox ('F') tracks exist
else if (!has_R && has_F) {
// Similarly, if only F tracks exist, N=1 must be possible (a fox).
cout << 1 << endl;
}
// Case 3: Both Rabbit ('R') and Fox ('F') tracks exist
else {
// Check if a path exists from (0,0) to (H-1, W-1) using only 'R' cells.
bool path_R_exists = check_path('R');
// Check if a path exists from (0,0) to (H-1, W-1) using only 'F' cells.
bool path_F_exists = check_path('F');
// If a path exists using only 'R' cells OR using only 'F' cells,
// then the minimum number of animals required is N=2.
// If path_R exists, sequence (F, R) could work.
// If path_F exists, sequence (R, F) could work.
// Based on simplified logic derived from analyzing the problem constraints and state updates.
if (path_R_exists || path_F_exists) {
cout << 2 << endl;
} else {
// If neither a pure 'R' path nor a pure 'F' path exists from start to end,
// then N=2 is not possible according to the logic.
// The minimal possible number N must be at least 3.
// Since the problem guarantees a solution exists, N=3 must be the minimum possible value.
cout << 3 << endl;
}
}
return 0;
}
