#include <bits/stdc++.h> using namespace std; /* In this question, every valid animal path starts at (1,1) and ends at (N,M) So any path that reaches any cell (x,y) can be extended to (N,M). answer= max​ of (min​ component switches on path P) over all paths P from (1, 1) to any other cell now this max is from (1, 1) to (N, M) always */ constexpr char UNTOUCHED('.'); constexpr int DIRNS(4); constexpr int MAX_SIZE(4000); constexpr int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1}; int n, m, depth[MAX_SIZE][MAX_SIZE]; // depth[i][j] = min no. of animals required to reach cell (i, j) from (0, 0) including (0, 0) and (i, j) = 1 + min. no of letter changes along any valid path from (0, 0) to (i, j) string snow[MAX_SIZE]; // input to be taken over here // Checks whether cell inside snow grid inline bool inside(int x, int y) { return (x >= 0 && x < n && y >= 0 && y < m && snow[x][y] != UNTOUCHED); } int main() { iostream::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; // n, m are globally declared where n is height and m is width for (int i = 0; i < n; i++) cin >> snow[i]; deque<pair<int, int>> q; q.emplace_back(0, 0); depth[0][0] = 1; while (!q.empty()) { auto [cx, cy] = q.front(); q.pop_front(); // Explore 4 neighboring cells for (int d = 0; d < DIRNS; d++) { int nx = cx + dx[d], ny = cy + dy[d]; // If neighbor is valid and not yet visited (depth == 0 means univisted) if (inside(nx, ny) && depth[nx][ny] == 0) { if (snow[nx][ny] == snow[cx][cy]) // Same animal { depth[nx][ny] = depth[cx][cy]; q.emplace_front(nx, ny); } else { depth[nx][ny] = depth[cx][cy] + 1; q.emplace_back(nx, ny); } } } } cout << depth[n-1][m-1]; }