Submission #64525125

---

Source Code Expand

#include <bits/stdc++.h>
#define rg register
using namespace std;
const int N = 2e6 + 10;
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9')
        f = (c == '-') ? -1 : 1, c = getchar();
    while(c >= '0' && c <= '9')
        x = x * 10 + c - 48, c = getchar();
    return f * x;
}
struct node {
    int v, id;
    bool operator<(const node& z) const { return v > z.v; }
};
struct node1 {
    int to, next, v;
} a[N * 4];
int dis[N], vis[N], head[N], cnt;
priority_queue<node> q;
void add(int x, int y, int v) {
    a[++cnt].next = head[x];
    a[cnt].to = y;
    a[cnt].v = v;
    head[x] = cnt;
}
void dij(int s) {
    q.push((node){0, s});
    memset(dis, 127, sizeof(dis));
    dis[s] = 0;
    while(!q.empty()) {
        int now = q.top().id;
        q.pop();
        if(vis[now])
            continue;
        vis[now] = 1;
        for(int i = head[now]; i; i = a[i].next) {
            int v = a[i].to;
            if(dis[v] > dis[now] + a[i].v)
                dis[v] = dis[now] + a[i].v, q.push((node){dis[v], v});
        }
    }
}
int n, m;
int calc(int x, int y) {
    return (x - 1) * m + y;
}
string s[1010];
int fx[10] = {0, 0, -1, 1, 0, 0, 2, -2};
int fy[10] = {1, -1, 0, 0, -2, 2, 0, 0};
int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            for(int k = 0; k <= 7; k++) {
                int x = fx[k] + i, y = fy[k] + j;
                if(x < 1 || y < 1 || x > n || y > m)
                    continue;
                if(s[x][y] == '#' || k >= 4)
                    add(calc(i, j), calc(x, y), 1);
                else
                    add(calc(i, j), calc(x, y), 0);
            }
        }
    int A = read(), B = read(), C = read(), D = read();
    dij(calc(A, B));
    cout << dis[calc(C, D)];
}

Submission Info

Judge Result