文章

20

粉丝

224

获赞

56

访问

136.7k

头像
题目中的“ t 秒时间内刚好充满”个人感觉有歧义,但是两种理解却都能 AC
P1126
发布于2022年2月15日 15:11
阅读数 5.6k

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

const int maxn = 30 + 2;
char mpt[maxn][maxn];  // 存储房间结构
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};  // 毒气的扩散方向:上、下、左、右

int n, m, t, x, y;  // 房间的高、宽、毒气扩散时间、表演的地点

struct node {
	int x, y;
};

// 使用广度优先搜索求解,返回值为真说明在 t 秒时间内毒气没有充满房间或刚好充满,输出现在房间里的情况,否则输出 NO
bool bfs(int x, int y, int t) {
	mpt[x][y] = '#';  // 首先设置表演地点位置有毒气
	queue<node> q;  // 使用队列来维护一层层发散的优先级
	q.push(node{x, y});
	while (t--) {
		int q_size = q.size();  // 当前队列里元素的个数,遍历当前队列的元素,将当前秒内房间的毒气进行扩散
		while (q_size--) {
			node now = q.front();
			q.pop();
			for (int i = 0; i < 4; ++i) {  // 上下左右四个方向
				int nx = now.x + dir[i][0];
				int ny = now.y + dir[i][1];
				// 保证扩散到的位置是位于房间内并且是还没被毒气充满的位置
				if (nx >= 1 & nx <= n & ny >= 1 & ny <= m & mpt[nx][ny] == '.') {
					mpt[nx][ny] = '#';
					q.push(node{nx, ny});
				}
			}
		}
		if (q.empty()) br...
登录查看完整内容


登录后发布评论

1 条评论
爱吃花朵汤圆
2023年6月7日 11:00

hh这个把所有情况都设成true,甚至也能ac

赞(0)