投资做网站利润分析,江苏易销 网站建设,怎样换网站关键词,.net网站开发源码注释Problem - 199D - Codeforces
题目大意#xff1a;有一个两个垂直的平行墙壁组成的一个峡谷。一个人初始是在左边墙壁第一层。在每个墙壁上有些障碍点#xff0c;用X表示#xff0c;这些障碍点不能被到达。#xff0c;他可以执行以下三个操作#xff1a;
向当前墙壁往上…Problem - 199D - Codeforces
题目大意有一个两个垂直的平行墙壁组成的一个峡谷。一个人初始是在左边墙壁第一层。在每个墙壁上有些障碍点用X表示这些障碍点不能被到达。他可以执行以下三个操作
向当前墙壁往上爬一层向当前墙壁往下爬一层向对面墙壁往上爬k层
同时初始时在第0层有水他每次执行完以上任意一个操作后水位会上升一层。求是否可以安全的到n层以上。
这题是一个游戏背景可能描述的不够清晰下面是DeepL的翻译 这题是一个显然的搜索用dfs或者bfs都可以实现。如果dfs和bfs都可以实现用bfs会更好
这题的思路就是用一个队列存入每次的当前层数、水位层数和在左边还是在右边 这三个变量。之后的处理跟其他bfs没有太大区别判断超界当前位置小于水位位置就continue根据在左墙壁或者在右墙壁进行判断即可。
代码如下
#include iostream
#include vector
#include string
#include cstring
#include set
#include map
#include queue
#include ctime
#include random
#include sstream
#include numeric
#include stdio.h
#include functional
#include bitset
#include algorithm
using namespace std;// #define Multiple_groups_of_examples
// #define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)-sync_with_stdio(false); // 开IOS需要保证只使用Cpp io流 *
#define dbgnb(a) std::cout #a a \n;
#define dbgtt cout !!!test!!! \n;
#define rep(i,x,n) for(int i x; i n; i)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pairint,int PII;const int INF 0x3f3f3f3f;
const int N 2e5 21;void inpfile();
void solve() {// 这个代码是从0开始的即 [0, n-1]int n,k; cinnk;string left,right; cinleftright;vectorvectorint vis(2, vectorint(n));vectorint fx{1,-1, k}; // 三个操作queuearrayint,3 q; // 当前位置水位位置左边还是右边q.push({0, 0, 0});// 布尔值判断是否已经可以合法的大于等于n了bool ok false;// 开始bfswhile(q.size()) {auto tmp q.front(); q.pop();// 记录上次的位置当前水位上次在那个墙壁int last tmp[0], water tmp[1] 1, fg tmp[2];// 进行判断for(int i 0; i 3; i) {int now last fx[i];ok | now n; // 如果now直接大于n了表示可以// 判断是否超界if(now 0 || now n) continue;// 判断是否现在位置 小于 水位 等于水位可以if(now water) continue;// 在左墙壁if(fg 0) {if(i 2) {// 已经到过了或者这个位置不能到达if(vis[fg][now] || left[now] X) continue;// 否则入队vis[fg][now] 1;q.push({now, water, 0});} else {// 也类似if(vis[!fg][now] || right[now] X) continue;vis[!fg][now] 1;q.push({now, water, 1});}} else { // 在右墙壁同上if(i 2) {if(vis[fg][now] || right[now] X) continue;vis[fg][now] 1;q.push({now, water, 1});} else {if(vis[!fg][now] || left[now] X) continue;vis[!fg][now] 1;q.push({now, water, 0});}}}}puts(ok ? YES : NO);
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif{#ifdef Multiple_groups_of_examplesint T; cinT;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen(ANSWER.txt, w,stdout);#endif
}
