// Problem Link: https://oj.uz/problem/view/BOI13_tracks #include <bits/stdc++.h> using namespace std; #define solution_01BFS #ifdef solution_DOUBT #define UNTOUCHED '.' constexpr int DIRNS(4); constexpr pair<int, int> MOVE[DIRNS]{{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; vector<vector<char>> meadow; // NOTE: Don't use variable name map as there exists std::map in C++ STL int count(int height, int width) { vector<vector<bool>> vis(height, vector<bool>(width)); int res = 0; for (int i = 0; i < height; i++) for (int j = 0; j < width; j++) { char curr_animal = meadow[i][j]; if (!vis[i][j] && curr_animal != UNTOUCHED) { vector<vector<bool>> curr(height, vector<bool>(width)); res++; stack<pair<int, int>> st; // h, w st.emplace(i, j); vis[i][j] = true; curr[i][j] = true; while (!st.empty()) { auto [h, w] = st.top(); st.pop(); for (int d = 0; d < DIRNS; d++) { int new_h = h + MOVE[d].first, new_w = w + MOVE[d].second; if (new_h >= 0 && new_h < height && new_w >= 0 && new_w < width && meadow[new_h][new_w] != UNTOUCHED) if (!vis[new_h][new_w] && meadow[new_h][new_w] == curr_animal) vis[new_h][new_w] = true, st.emplace(new_h, new_w), curr[new_h][new_w] = true; else if (vis[new_h][new_w] && !curr[new_h][new_w]) // IMP: else ALWAYS MATHES NEAREST UNMATCHED if st.emplace(new_h, new_w), curr[new_h][new_w] = true; } } } } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; cin >> H >> W; meadow.assign(H, vector<char>(W)); for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> meadow[i][j]; cout << count(H, W) << '\n'; return 0; } #endif #ifdef solution_01BFS /* 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, ans = 1, 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(); // Track maximum animals needed so far ans = max(ans, depth[cx][cy]); // 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 << ans << '\n'; } #endif