Minecraft

#include <bits/stdc++.h>

struct solve {
    int x, y, d;
    solve(int x1, int y1, int d1)
    : x(x1), y(y1), d(d1)
    {
    }
};

constexpr int MAX = 502;

int n, m;
int s, t, u, v;
char mat[MAX][MAX];
int memo[MAX][MAX];

void bfs( ) {
    std::queue<solve> cola;
    cola.push(solve( s, t, 0 ));

    do {
        solve actual = cola.front( );
        cola.pop( );

        if (actual.x == u && actual.y == v) {
            memo[u][v] = std::min(memo[u][v], actual.d);
        }

        std::pair<int, int> vecinos[] = {
            { actual.x + 1, actual.y },
            { actual.x - 1, actual.y },
            { actual.x, actual.y + 1 },
            { actual.x, actual.y - 1 }
        };

        for (auto it : vecinos) {
            int dx = it.first;
            int dy = it.second;
            if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && mat[dx][dy] != '#') {
                if (mat[dx][dy] == '.' && (actual.d + 1) < memo[dx][dy]) {
                    cola.push(solve( dx, dy, actual.d + 1 ));
                    memo[dx][dy] = actual.d + 1;
                } else if (mat[dx][dy] != '.') {
                    int costo = (mat[dx][dy] - '0') + 1;
                    if (actual.d + costo < memo[dx][dy]) {
                        cola.push(solve( dx, dy, actual.d + costo ));
                        memo[dx][dy] = actual.d + costo;
                    }
                }
            }
        }
    } while (!cola.empty( ));
}

int main( ) {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    std::fill(&memo[0][0], &memo[MAX][0], INT_MAX);

    std::cin >> n >> m >> s >> t >> u >> v;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            char op;
            std::cin >> op;
            mat[i][j] = op;
        }
    }
    bfs( );
    std::cout << memo[u][v] << '\n';
}