数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++代码检查蚱蜢能否到达目标
假设我们有一个大小为n的字符串S和另一个数字k。该字符串包含四种类型的字符。假设有一些单元格，一只蚱蜢想要跳跃以到达目标。字符“.”表示相应的单元格为空，字符“#”表示相应的单元格包含障碍物，蚱蜢不能跳到那里。“G”表示蚱蜢从该位置开始，“T”表示目标单元格。蚱蜢能够从其当前位置跳跃正好k个单元格。我们必须检查蚱蜢是否可以跳到目标。
因此，如果输入类似于S = "#G#T#"; k = 2，则输出将为True，因为从G到T有2个单元格，而k为2，所以蚱蜢可以通过一次跳跃到达那里。
步骤
为了解决这个问题，我们将遵循以下步骤：
n := size of S x := position of 'G' in S y := position of 'T' in S if x > y, then: swap x and y for initialize i := x, when i < y, update i := i + k, do: if S[i] is same as '#', then: Come out from the loop if i is same as y, then: return true Otherwise return false
示例
让我们看看以下实现以获得更好的理解：
#include <bits/stdc++.h>
using namespace std;
bool solve(string S, int k){
int n = S.size();
int i;
int x = S.find('G');
int y = S.find('T');
if (x > y)
swap(x, y);
for (i = x; i < y; i += k){
if (S[i] == '#')
break;
}
if (i == y)
return true;
else
return false;
}
int main(){
string S = "#G#T#";
int k = 2;
cout << solve(S, k) << endl;
}输入
"#G#T#", 2
输出
1
更新于: 2022年3月29日
247 次查看
广告