30分求助,悬赏关注,谢谢!
查看原帖
30分求助,悬赏关注,谢谢!
546681
lcbridgeAK CSP-S楼主2022/11/22 16:16
#include <bits/stdc++.h>
using namespace std;
int n, m, sx, ex, sy, ey, flag, a[55][55];
bool vis[55][55];
char s;
struct Pos {
	int x, y, step;
	char f;
	Pos(int a, int b, int c, char d) {
		x = a;
		y = b;
		step = c;
		f = d;
	}
};
void bfs() {
	queue <Pos> q;
	q.push(Pos(sx, sy, 0, s));
	while (!q.empty()) {
		Pos now = q.front();
		q.pop();
		int x = now.x, y = now.y, step = now.step;
		char f = now.f;
		if (x <= 1 || x >= n || y <= 1 || y >= m)continue;
		if (a[x][y] || vis[x][y])continue;
		if (x == ex && y == ey) {
			flag = 1;
			cout << step;
			return ;
		}
		vis[x][y] = 1;
		if (f == 'E') {
			if (!a[x + 1][y])q.push(Pos(x + 1, y, step + 1, 'E'));
			else if (!a[x + 1][y] && !a[x + 2][y])q.push(Pos(x + 2, y, step + 1, 'E'));
			else if (!a[x + 1][y] && !a[x + 2][y] && !a[x + 3][y])q.push(Pos(x + 3, y, step + 1, 'E'));
			q.push(Pos(x, y, step + 1, 'N'));
			q.push(Pos(x, y, step + 1, 'S'));
		} else if (f == 'W') {
			if (!a[x - 1][y])q.push(Pos(x - 1, y, step + 1, 'W'));
			else if (!a[x - 1][y] && !a[x - 2][y])q.push(Pos(x - 2, y, step + 1, 'W'));
			else if (!a[x - 1][y] && !a[x - 2][y] && !a[x - 3][y])q.push(Pos(x - 3, y, step + 1, 'W'));
			q.push(Pos(x, y, step + 1, 'S'));
			q.push(Pos(x, y, step + 1, 'N'));
		} else if (f == 'N') {
			if (!a[x][y - 1])q.push(Pos(x, y - 1, step + 1, 'N'));
			else if (!a[x][y - 1] && !a[x][y - 2])q.push(Pos(x, y - 2, step + 1, 'N'));
			else if (!a[x][y - 1] && !a[x][y - 2] && !a[x][y - 3])q.push(Pos(x, y - 3, step + 1, 'N'));
			q.push(Pos(x, y, step + 1, 'E'));
			q.push(Pos(x, y, step + 1, 'W'));
		} else if (f == 'S') {
			if (!a[x][y + 1])q.push(Pos(x, y + 1, step + 1, 'S'));
			else if (!a[x][y + 1] && !a[x][y + 2])q.push(Pos(x, y + 2, step + 1, 'S'));
			else if (!a[x][y + 1] && !a[x][y + 2] && !a[x][y + 3])q.push(Pos(x, y + 3, step + 1, 'S'));
			q.push(Pos(x, y, step + 1, 'W'));
			q.push(Pos(x, y, step + 1, 'E'));
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	cin >> sx >> sy >> ex >> ey >> s;
	bfs();
	if (!flag)cout << "-1";
	return 0;
}

记录

2022/11/22 16:16
加载中...