Submission #64976864

---

Source Code Expand

#include <stdio.h>
#include <string.h>

int H, W;
char S[1024][1024];
int A, B, C, D;

const int d[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int mincost[1024][1024][5];

struct q_s {
	int y, x;
	int mg;
} q[1024 * 1024 * 5 * 2];

int main(void) {
	int i;
	int qs = 1024 * 1024 * 5, qe = 1024 * 1024 * 5;
	int ans;
	if (scanf("%d%d", &H, &W) != 2) return 1;
	for (i = 1; i <= H; i++) {
		if (scanf("%1022s", S[i] + 1) != 1) return 1;
	}
	if (scanf("%d%d%d%d", &A, &B, &C, &D) != 4) return 1;

	memset(mincost, 0x7f, sizeof(mincost));
	mincost[A][B][4] = 0;
	q[qe++] = (struct q_s){ A, B, 4 };
	while (qs < qe) {
		struct q_s cur = q[qs++];
		int curcost = mincost[cur.y][cur.x][cur.mg];
		for (i = 0; i < 4; i++) {
			int ny = cur.y + d[i][0], nx  = cur.x + d[i][1];
			if (ny <= 0 || H < ny || nx <= 0 || W < nx) continue;
			/* 普通に行く */
			if (S[ny][nx] == '.' || cur.mg == i) {
				if (mincost[ny][nx][4] > curcost) {
					mincost[ny][nx][4] = curcost;
					q[--qs] = (struct q_s){ ny, nx, 4 };
				}
			}
			/* 前蹴りをして行く */
			if (mincost[ny][nx][i] > curcost + 1) {
				mincost[ny][nx][i] = curcost + 1;
				q[qe++] = (struct q_s){ ny, nx, i };
			}
		}
	}
	ans = mincost[C][D][0];
	for (i = 1; i < 5; i++) {
		if (mincost[C][D][i] < ans) ans = mincost[C][D][i];
	}
	printf("%d\n", ans);
	return 0;
}

/*

前蹴りをした後は必ずそっちの方向に移動するとする
→ 前蹴りをした後の移動では、前蹴りをした方向を記録
→ 次回、その方向にはタダで行ける

コスト0とコスト1の遷移がある → 0-1BFS

*/

Submission Info

Judge Result