求助,bfs,为什么第二个点MLE了啊
查看原帖
求助,bfs,为什么第二个点MLE了啊
249422
TinyMirror1楼主2020/10/10 14:42
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
string s[101];
int Move[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
int n, m, cnt[101][101], vis[101][101];
int sx = -1, sy;
bool in(int x, int y) {
	return x >= 0 && x < n && y >= 0 && y < m;
}
struct node {
	int x, y, cnt, dir;
	node(int xx, int yy, int cc, int dd) {
		x = xx, y = yy, cnt = cc, dir = dd;
	}
};
queue<node> q;
void bfs(int x, int y) {
	q.push(node(x, y, -1, -1));
	vis[x][y] = true;
	while (!q.empty()) {
		node now = q.front();
		if (now.x == sx && now.y == sy) {
			cout << now.cnt;
			return;
		}
		q.pop();
		for (int i = 0; i < 4; i++) {
			int tx = now.x + Move[i][0];
			int ty = now.y + Move[i][1];
			if (in(tx, ty) && !vis[tx][ty] && s[tx][ty] != '*') {
				if (now.dir == i) {
					while (in(tx, ty) && s[tx][ty] != '*') {
						q.push(node(tx, ty, now.cnt, i));
						tx += Move[i][0], ty += Move[i][1];
						vis[now.x][now.y] = true;
					}
				} else {
					q.push(node(tx, ty, now.cnt + 1, i));
					vis[now.x][now.y] = true;
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin >> m >> n;
	
	memset(cnt, 0x7f, sizeof(cnt));
	for (int i = 0; i < n; i++) cin >> s[i];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (sx != -1 && s[i][j] == 'C') {
				bfs(i, j);
				return 0;
			}
			if (s[i][j] == 'C') {
				sx = i; sy = j;
			}
		}
	}
	return 0;
}
2020/10/10 14:42
加载中...