E_Stronger_Takahashi.cpp

#include <bits/stdc++.h>
using namespace std;
// First you make it work, then you can always make it beautiful
const int inf = 1e9;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> v(n);
    for(int i=0;i<n;i++) cin >> v[i];

    int dist[n][m];
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) dist[i][j] = inf;
    }

    queue<pair<int, int>> q;
    q.push({0, 0});
    dist[0][0] = 0;

    while(!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        for(int i=-2;i<=2;i++) {
            for(int j=-2;j<=2;j++) {
                if(abs(i) == 2 && abs(j) == 2) continue;
                int nx = x + i;
                int ny = y + j;
                if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                int cost = (v[nx][ny] == '.' && abs(i) + abs(j) <= 1) ? 0 : 1;
                if(dist[nx][ny] > dist[x][y] + cost) {
                    dist[nx][ny] = dist[x][y] + cost;
                    q.push({nx, ny});
                }
            }
        }
    }

    cout << dist[n-1][m-1];


    return 0;
}