Submission #64575969

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
constexpr int dxUlt[4] = {2, 0, -2, 0}, dyUlt[4] = {0, 2, 0, -2};
constexpr int MAXN = 1010, INF = 0x7f7f7f7f, MAXM = 1e6 + 10;

int n, m, stx, sty, edx, edy, idx;
char Gew[MAXN][MAXN];
int Head[MAXM], dis[MAXM];
bool vis[MAXM];

struct Graph {
	int v, w, nxt;
	Graph (int v = 0, int w = 0, int nxt = 0):v(v), w(w), nxt(nxt){};
} Edge[12000005];

inline void AddEdge (int u, int v, int w) { Edge[idx] = Graph (v, w, Head[u]), Head[u] = idx ++; }

#define getID(x,y) ((x - 1) * m + y)
inline void MK_Edge (int x, int y) {
	int u = getID (x, y);
	for (int i = 0; i < 4; i ++) {
		int nx = x + dx[i], ny = y + dy[i], v = getID (nx, ny);
		if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
		if (Gew[nx][ny] == '#') {
			AddEdge (u, v, 1);
			int nxUlt = x + dxUlt[i], nyUlt = y + dyUlt[i], vUlt = getID (nxUlt, nyUlt);
			if (nxUlt < 1 || nxUlt > n || nyUlt < 1 || nyUlt > m || Gew[nxUlt][nyUlt] == '.') continue;
			AddEdge (u, vUlt, 1);
		} else {
			AddEdge (u, v, 0);
		}
	}
}

#define pii pair<int,int>
#define mkp make_pair
inline void dijkstra (int st, int ed) {
	priority_queue <pii, vector<pii>, greater<pii>> q;
	fill (dis, dis + n * m + 1, INF);
	fill (vis, vis + n * m + 1, false);
	dis[st] = 0, q.push (mkp (dis[st], st));
	while (!q.empty()) {
		int u = q.top().second; q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = Head[u]; ~i; i = Edge[i].nxt) {
			int v = Edge[i].v, w = Edge[i].w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push (mkp (dis[v], v));
			}
		}
	}
	cout << dis[ed] << "\n";
	return;
}

signed main() {
//	freopen ("data.txt", "r", stdin);
//	freopen ("ABC400.out", "w", stdout);
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0) -> sync_with_stdio(0);
    cin >> n >> m, memset (Head, -1, sizeof (Head));
    for (int i = 1; i <= n; i ++) {
    	for (int j = 1; j <= m; j ++) 
    		cin >> Gew[i][j];
	}
	cin >> stx >> sty >> edx >> edy;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++)
			MK_Edge (i, j);
	}
	dijkstra (getID (stx, sty), getID (edx, edy));
	return 0;
}

Submission Info

Judge Result