CodeForces - 735A Ostap and Grasshopper (BFS)
简单题，用的广搜
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
int n,k;
string s;
int start,end;
bool vis[105];
queue<int> q;
int flag;
void BFS()
{
flag=0;
q.push(start);
while(!q.empty())
{
int t1=q.front();
q.pop();
int temp;
for(int i=0;i<=1;i++)
{
// printf("%d\n",temp);
if(i)
{
temp=t1+k;
if(temp>n||vis[temp]||s[temp]=='#') continue;
}
else
{
temp=t1-k;
if(temp<0||vis[temp]||s[temp]=='#') continue;
}
if(temp==end){
flag=1;
break;
}
q.push(temp);
// printf("%d\n",temp);
vis[temp]=true;
}
if(flag) break;
}
}
int main(void)
{
cin>>n>>k;
cin>>s;
for(int i=0;i<s.length();i++)
{
vis[i]=false;
if(s[i]=='G') start=i;
if(s[i]=='T') end=i;
}
vis[start]=true;
BFS();
if(flag) printf("YES\n");
else printf("NO\n");
return 0;
}
