80分 #1 WA
  • 板块P3395 路障
  • 楼主xlege
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/18 13:06
  • 上次更新2023/11/18 14:54:41
查看原帖
80分 #1 WA
1187580
xlege楼主2023/11/18 13:06

请教,第1个WA,请帮忙指出哪句代码错了,怎样改。谢谢!

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int dir[][2] = { -1, 0, 1, 0, 0, -1, 0, 1 };
struct Node { int x, y, step; } node;
int t, n;

bool bfs(vector<pair<int, int>>& group) {
	vector<vector<int>> board(n, vector<int>(n, 0));
	vector<vector<int>> visited(n, vector<int>(n, 0));
	visited[0][0] = 1;
	queue<Node> q;
	q.push({ 0, 0, 0 });
	int last_step = 0;
	while (!q.empty()) {
		node = q.front();
		if (node.x == n - 1 && node.y == n - 1) return true;
		q.pop();

		if (node.step > last_step) {
			board[group[last_step].second][group[last_step].first] = 1;
			last_step = node.step;
		}
		for (int i = 0; i < 4; i++) {
			int new_x = node.x + dir[i][0], new_y = node.y + dir[i][1];
			if (new_x == n - 1 && new_y == n - 1)
				return true;
			if (new_x < 0 || new_x >= n || new_y < 0 || new_y >= n || board[new_y][new_x]) continue;
			if (visited[new_y][new_x]) continue;
			q.push({ new_x, new_y, node.step + 1 });
			visited[new_y][new_x] = 1;
		}
	}
	return false;
}

int main() {
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		vector<pair<int, int>> v;
		for (int j = 0, a, b; j < 2 * n - 2; j++) {
			cin >> a >> b;
			v.push_back({ a - 1, b - 1 });
		}
		cout << (bfs(v) ? "Yes" : "No") << endl;
	}
	return 0;
}
2023/11/18 13:06
加载中...