c.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAXN = 1e3 + 10;
char field[MAXN][MAXN];
bool was[MAXN][MAXN];
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
queue <pair <int, int> > q[10000];

int n, m;
bool check(int x, int y){
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}

void solve(){

    cin >> n >> m;

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> field[i][j];
        }
    }
    q[0].push({1, 1});
    int timer = 0;
    while (!q[timer].empty()){

        while (!q[timer].empty()){
            pair <int, int> z = q[timer].front();
            q[timer].pop();
            int vx = z.f;
            int vy = z.s;
            for (int i = 0; i < 4; i++){
                int tox = vx + dx[i];
                int toy = vy + dy[i];
                if (check(tox, toy) && !was[tox][toy] && field[vx][vy] == field[tox][toy]){
                    q[timer].push({tox, toy});
                    //dist[tox][toy] = dist[vx][vy];
                    was[tox][toy] = 1;
                }
                if (check(tox, toy) && !was[tox][toy] && field[vx][vy] != field[tox][toy] && field[tox][toy] != '*'){
                    q[timer + 1].push({tox, toy});
                    //dist[tox][toy] = dist[vx][vy];
                    was[tox][toy] = 1;
                }
            }
        }
        timer++;
    }
    cout << timer;
}

int main() {

    IOS;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}