#include <iostream> #include <vector> #include <queue> using namespace std; struct heap { int i, j, w; bool operator < (const heap &o) const { return w > o.w; } }; vector<pair<int, int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<string> grid(n); for (auto &s:grid) cin >> s; auto invalid = [&](int i, int j) -> bool { return i < 0 || i >= n || j < 0 || j >= m; }; priority_queue<heap> pq; vector<vector<bool>> vis(n, vector<bool>(m, false)); pq.push({0, 0, grid[0][0] == 'F'}); while (!pq.empty()){ auto [i, j, W] = pq.top(); pq.pop(); if (vis[i][j]) continue; vis[i][j] = true; if (i == n - 1 && j == m - 1){ cout << W + 1 << '\n'; return 0; } for (auto [di, dj]:dir){ if (invalid(i + di, j + dj)) continue; pq.push({i + di, j + dj, W + (grid[i][j] != grid[i + di][j + dj])}); } } }