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

Arnab Chakraborty

更新于: 2022年3月29日

247 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习