#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int MAX_SIZE = 4444; // Define maximum grid size
char meadow[MAX_SIZE][MAX_SIZE]; // Grid to hold the characters representing the meadow
bool visited[MAX_SIZE][MAX_SIZE]; // Visited array to track which cells have been processed
int dx[4] = {1, -1, 0, 0}; // Direction vectors for row movements (down, up)
int dy[4] = {0, 0, 1, -1}; // Direction vectors for column movements (right, left)
pair<int, int> parent[MAX_SIZE][MAX_SIZE]; // Array to store parent coordinates for each cell
int level[MAX_SIZE][MAX_SIZE]; // Array to store the level (or component ID) for each cell
bool levelVisited[MAX_SIZE * MAX_SIZE]; // Array to check if a level has been visited
signed main() {
int n, m; // Dimensions of the grid
cin >> n >> m; // Input the dimensions of the meadow
// Input the characters into the meadow grid
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> meadow[i][j];
}
}
queue<pair<int, int>> sameTypeQueue; // Queue for cells of the same type
queue<pair<int, int>> differentTypeQueue; // Queue for cells of different types (tracks)
// Start BFS from the bottom-right corner of the grid
sameTypeQueue.push({n, m});
int distinctLevels = 1; // Initialize distinct animal count
while (!(sameTypeQueue.empty() && differentTypeQueue.empty())) {
int y, x; // Current cell coordinates
// Process cells from the same type queue
if (!sameTypeQueue.empty()) {
y = sameTypeQueue.front().ff;
x = sameTypeQueue.front().ss;
sameTypeQueue.pop();
if (visited[y][x]) continue; // Skip if already visited
}
// Process cells from the different type queue
else {
y = differentTypeQueue.front().ff;
x = differentTypeQueue.front().ss;
differentTypeQueue.pop();
if (!visited[y][x]) { // If cell is not visited
int parentY = parent[y][x].ff; // Get parent coordinates
int parentX = parent[y][x].ss;
// Check if the parent level is visited; if not, increment distinct animal count
if (!levelVisited[level[parentY][parentX]]) {
distinctLevels++;
}
levelVisited[level[parentY][parentX]] = true; // Mark this level as visited
}
}
// Continue if out of bounds
if (y < 1 || y > n || x < 1 || x > m) continue;
visited[y][x] = true; // Mark the current cell as visited
level[y][x] = distinctLevels; // Assign the current level to the cell
// Explore neighboring cells
for (int i = 0; i < 4; i++) {
int newY = y + dy[i]; // New row coordinate
int newX = x + dx[i]; // New column coordinate
if (!visited[newY][newX]) { // If the neighboring cell is not visited
if (meadow[newY][newX] == meadow[y][x]) { // Same type
sameTypeQueue.push({newY, newX}); // Add to same type queue
}
else if (meadow[newY][newX] == 'F' || meadow[newY][newX] == 'R') { // Different type (tracks)
parent[newY][newX] = {y, x}; // Set parent of this cell
differentTypeQueue.push({newY, newX}); // Add to different type queue
}
}
}
}
cout << distinctLevels; // Output the count of distinct animals (connected components)
return 0;
}
