当前位置: 首页> 健康> 知识 > 齐家装饰公司官网_如何发布网站_facebook海外推广_王通seo

齐家装饰公司官网_如何发布网站_facebook海外推广_王通seo

时间:2025/7/11 14:36:21来源:https://blog.csdn.net/zqystca/article/details/144176664 浏览次数:0次
齐家装饰公司官网_如何发布网站_facebook海外推广_王通seo

题目:

https://www.luogu.com.cn/problem/P3395

题目描述

B 君站在一个 n×n 的棋盘上。最开始,B君站在 (1,1) 这个点,他要走到(n,n) 这个点。

B 君每秒可以向上下左右的某个方向移动一格,但是很不妙,C 君打算阻止 B 君的计划。

每秒结束的时刻,C 君 会在 (x,y) 上摆一个路障。B 君不能走在路障上。

B 君拿到了 C 君准备在哪些点放置路障。所以现在你需要判断,B 君能否成功走到 (n,n)。

保证数据足够弱:也就是说,无需考虑“走到某处然后被一个路障砸死”的情况,因为答案不会出现此类情况。

输入格式

首先是一个正整数 T,表示数据组数。

对于每一组数据:

第一行,一个正整数 n。

接下来 2*n−2 行,每行两个正整数 x 和 y,意义是在那一秒结束后(x,y) 将被摆上路障。

输出格式

对于每一组数据,输出 Yes 或 No,回答 B 君能否走到 (n,n)。

奇妙思路:借鉴了洛谷 P10491陨石砸牧场,但是这题是先走路再放障碍物的,并且强调不会砸死。我不能理解不能砸死的情况(因为有这种可能),这题的障碍物放置的时间不能类似陨石那题,它要统一+1,因为是先走再放,我们模拟下,如果走一步为1秒,第2秒放置障碍物(不能是第一秒放)。走第二秒的时候才进行判断,1+1<2是不成立的,所以本就是不能走的。此外,在队列里取出队首数据,就可以将它出队列了。

代码如下:

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;int dx[] = {1, 0, -1, 0}; // 方向数组 
int dy[] = {0, -1, 0, 1};int T;
int n; // 地图大小(n x n)
int times[1005][1005]; // 储存路障出现时间点(0表示无路障)
int steps[1005][1005]; // 记录到达每个位置的最小步数(-1表示未访问)
bool res[1005]; // 储存每组测试用例的结果
struct Node{int x;int y;
};
queue<Node> q;bool bfs(int startX, int startY){Node start = {startX, startY};q.push(start);steps[startX][startY] = 0; // 起点步数为0while (!q.empty()) {Node currenthead = q.front();//取出当前队首数据 q.pop();//取出队首数据就可以出队了 int x = currenthead.x;int y = currenthead.y;if (x == n && y == n) {return true; // 到达终点}for (int k = 0; k < 4; k++) {int tx = x + dx[k];int ty = y + dy[k];if (tx >= 1 && tx <= n && ty >= 1 && ty <= n) // 基本检查边界{ if ((steps[x][y] + 1 < times[tx][ty] || times[tx][ty] == 0) && steps[tx][ty] == -1)//检查到达探索点的时间是否小于放置障碍物的时间,以及该点是否探索过。-1为探索过 {steps[tx][ty] = steps[x][y] + 1; Node newNode = {tx, ty};q.push(newNode);}}}}return false; // 无法到达终点
}int main()
{cin >> T;for (int i = 1;  i <= T; i++){cin >> n;memset(times, 0, sizeof(times)); memset(steps, -1, sizeof(steps)); for (int i = 1; i <= 2 * n - 2; i++) { int x, y;cin >> x >> y;times[x][y] = i + 1; // 障碍物放置时间,这里i+1是因为我们想要的是第i步后放置的障碍物.}res[i] = bfs(1, 1); // 从(1,1)开始BFS,结果存入res数组}for (int i = 1; i <= T; i++){if (res[i])cout << "Yes" << endl;elsecout << "No" << endl;}return 0;
}

关键字:齐家装饰公司官网_如何发布网站_facebook海外推广_王通seo

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: