求助,孩子真不会了,呜呜
查看原帖
求助,孩子真不会了,呜呜
519335
konodioda1楼主2021/8/23 10:56
#include<bits/stdc++.h>

#define FA ios::sync_with_stdio(false); cin.tie(NULL)
using namespace std;
#define mp make_pair
using vi = vector<int>;
using LL = long long;
using pii = pair<int, int>;
const int maxn = 1e5 + 50;
const double pi = 3.1415926;
const int inf = 1e9;


int b[55][55];
int n, m;
int p1, q1, p2, q2;
char d;
unordered_map<char, int>occ{ {'S', 1}, {'E', 2},{'N', 3}, {'W', 4} };
struct Node {
	int x, y;
	char d;
	Node(int xx, int yy, char dd) : x(xx), y(yy), d(dd) {}
};
//             S  E   N  W
int dx[] = { 0, 1, 0, -1, 0 };
int dy[] = { 0, 0, 1, 0, -1 };
bool check(int x, int y) {
	if (x < 1 || x >= n || y < 1 || y >= m)   return true;
	if (b[x][y] == 1 || b[x + 1][y] == 1 || b[x][y + 1] == 1 || b[x + 1][y + 1] == 1)   return true;
	return false;
}
bool findAns(int x, int y) {
	return x == p2 && y == q2;
}
void solve() {
	int cnt = 0, ans = -1;
	queue<Node>que;
	que.push(Node(p1, q1, d));
	while (!que.empty()) {
		int cap = que.size();
		for (int t = 0; t < cap; ++t) {
			Node cur = que.front(); que.pop();
			int x = cur.x, y = cur.y, d = cur.d;
			if (check(x, y))    continue;
			if (findAns(x, y)) {
				ans = cnt;
				break;
			}
			if (b[x][y] & (1 << occ[d]))	continue;
			b[x][y] |= (1 << occ[d]);
			if (d == 'S') {
				for (int i = 1; i <= 3; ++i) {
					que.push(Node(x + i * dx[1], y + i * dy[1], d));
				}
				que.push(Node(x, y, 'E'));
				que.push(Node(x, y, 'W'));
			}
			else if (d == 'E') {
				for (int i = 1; i <= 3; ++i) {
					que.push(Node(x + i * dx[2], y + i * dy[2], d));
				}
				que.push(Node(x, y, 'N'));  que.push({ x, y, 'S' });
			}
			else if (d == 'N') {
				for (int i = 1; i <= 3; ++i) {
					que.push(Node(x + i * dx[3], y + i * dy[3], d));
				}
				que.push({ x, y, 'W' });  que.push({ x, y, 'E' });
			}
			else {
				for (int i = 1; i <= 3; ++i) {
					que.push(Node(x + i * dx[4], y + i * dy[4], d));
				}
				que.push({ x, y, 'S' });  que.push({ x, y, 'N' });
			}
			
		}
		if (ans != -1)  break;
		cnt++;
	}
	cout << cnt << endl;
}

int main() {
	FA;
	
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j)    cin >> b[i][j];
	}
	cin >> p1 >> q1 >> p2 >> q2 >> d;
	solve();
	return 0;
}

2021/8/23 10:56
加载中...