E-Stronger Takahashi, 0-1 BFS

#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vpi;
typedef pair<int, int> pi;
#define f first
#define s second
#define pb push_back
#define endl "\n"
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
const int mod1 = 1e9 + 7, mod2 = 998244353, INF = 2e18, N = 2e5 + 5, L = 19;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
// -----------------------------------------------------------------------------

void solve()
{
    int n, m;
    cin >> n >> m;
    char grid[n + 1][m + 1];
    int cost[n + 1][m + 1];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> grid[i][j];
        }
    }
    for (int i = 0; i <= n; i++)
    {
        fill(cost[i], cost[i] + m + 1, INF);
    }
    function<bool(int, int)> inside = [&](int x, int y)
    {
        return (x >= 1 && x <= n && y >= 1 && y <= m);
    };
    deque<pi> dq;
    cost[1][1] = 0;
    dq.push_back({1, 1});
    // go, then punch
    while (!dq.empty())
    {
        auto [x, y] = dq.front();
        dq.pop_front();
        // 0 cost
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (inside(nx, ny))
            {
                // 0 costs
                if (grid[nx][ny] == '.' && cost[nx][ny] > cost[x][y])
                {
                    cost[nx][ny] = cost[x][y];
                    dq.push_front({nx, ny});
                }
                // 1 cost
                else
                {
                    // punch a 2x2 grid
                    for (int j = -1; j <= 1; j++)
                    {
                        for (int k = -1; k <= 1; k++)
                        {
                            int nnx = nx + j, nny = ny + k;
                            if (inside(nnx, nny) && cost[nnx][nny] > cost[x][y] + 1)
                            {
                                cost[nnx][nny] = cost[x][y] + 1;
                                dq.push_back({nnx, nny});
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = cost[n][m];
    cout << ((ans == INF) ? -1 : ans) << endl;
    return;
}

signed main()
{
    // __START__;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    // __END__;
    return 0;
}