#include <bits/stdc++.h>
#include <Windows.h>
using namespace std;
const int N = 1e4 + 5, M = 1e4 + 5;
int n, m, x, y, s, e, ansa, ansd;
int dist[N][M], mov[][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {-1, 1}, {-1, -1}, {1, -1}, {1, 1}}, cost[] = {10, 10, 10, 10, 14, 14, 14, 14};
bool gra, vis[N][M], in[N][M], a[N][M];
double ta, td;
LARGE_INTEGER Freq, BeginTimeA, EndTimeA, BeginTimeD, EndTimeD;
class Node{
	public:
		int x, y, cos, img;
		bool operator < (const Node &oth) const {
			if (cos + img != oth.cos + oth.img) 
				return cos + img > oth.cos + oth.img;
			else
				return cos > oth.cos;
		}
};

struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return (x ^ (x >> 31));
	}
	
	size_t operator()(uint64_t) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
	
};

//unordered_map<int, int, custom_hash> mp;

int f(int x, int y) { return ((abs(s - x) + abs(e - y)) * 10); }

void astar() {
	QueryPerformanceFrequency(&Freq);
	QueryPerformanceCounter(&BeginTimeA);
	memset(vis, 0, sizeof vis);
	priority_queue<Node> Q;
	Q.push((Node){x, y, 0, f(x, y)});
	in[x][y] = true;
	while (!Q.empty()) {
		Node t = Q.top();
		Q.pop();
		int x = t.x, y = t.y;
		if (x == s && y == e)
			break;
		if (vis[x][y])
			continue;
		vis[x][y] = true;
		for (int i = 0; i < 8; i++) {
			int dx = x + mov[i][0], dy = y + mov[i][1];
			if (dx < 1 || dx > n || dy < 1 || dy > m || vis[dx][dy] || (gra && a[dx][dy])) continue;
			dist[dx][dy] = t.cos + cost[i];
			in[dx][dy] = true;
			Q.push((Node){dx, dy, dist[dx][dy], f(dx, dy)});
		}
	}
	ansa = dist[s][e];
	QueryPerformanceCounter(&EndTimeA);
	ta = (double)(EndTimeA.QuadPart - BeginTimeA.QuadPart) / (double)(Freq.QuadPart);
}

void dijkstra() {
	QueryPerformanceFrequency(&Freq);
	QueryPerformanceCounter(&BeginTimeD);
	memset(vis, 0, sizeof vis);
	memset(dist, 0x3f, sizeof dist);
	priority_queue<Node> Q;
	Q.push((Node){x, y, 0, 0});
	dist[x][y] = 0;
	in[x][y] = true;
	while (!Q.empty()) {
		Node t = Q.top();
		Q.pop();
		int x = t.x, y = t.y;
//		cout << x << " " << y << " " << t.cos << "\n";
		if (vis[x][y]) 
			continue;
		vis[x][y] = true;
		for (int i = 0; i < 8; i++) {
			int dx = x + mov[i][0], dy = y + mov[i][1];
			if (dx < 1 || dx > n || dy < 1 || dy > m || vis[dx][dy] 
				|| dist[dx][dy] <= t.cos + cost[i] || (gra && a[dx][dy])) continue;
//			cout << dx << " " << dy << " " << x << " " << y << " " << cost[i] << " " << t.cos << " " << i << "\n";
			dist[dx][dy] = t.cos + cost[i];
			in[dx][dy] = true;
			Q.push((Node){dx, dy, dist[dx][dy], 0});
		} 
	}
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= m; j++) {
//			cout << dist[i][j] << " ";
//		}
//		cout << "\n";
//	}
	ansd = dist[s][e];
	QueryPerformanceCounter(&EndTimeD);
	td = (double)(EndTimeD.QuadPart - BeginTimeD.QuadPart) / (double)(Freq.QuadPart);
}

int main() {
	cin >> n >> m >> x >> y >> s >> e >> gra;
	if (gra) 
		while (1) {
			for (int i = 1; i <= n; i++) 
				for (int j = 1; j <= m; j++) 
					cin >> a[i][j];
			if (a[x][y] != 1) break;
			else {
				cout << "out of law!";
				system("pause");
				system("cls");
			}
		}
	astar();
	dijkstra();
	cout << "a* use " << fixed << ta * 1000 << " ms and its ans is " << ansa << ".\n";
	cout << "dijkstra use " << fixed << td * 1000 << " ms nad its ans is " << ansd;
	return 0;
} 

附结果：（当图的大小到达1000*1000时）

1000 1000 1 1 1000 1000 0

a* use 31.802900 ms and its ans is 13986.

dijkstra use 574.183700 ms nad its ans is 13986