跳坑小能手
Time Limit: 2000/1000ms (Java/Others)
Problem Description:
GDUFE-GAME现场有一个游戏场地人头窜动,围观参与游戏的学生在场上跳来跳去。每次游戏一名参与者,且每次游戏结束时场地都会出现随机的变化(游戏过程中场地不会发生变化,只在更换参与者时变化)。场地有两种类型:第一种是高台,第二种是深坑。参与者从任意高台出发向前跳,规定每次向前跳的步伐大小相同,但步伐大小由参与者自行决定,必须大于0。只要跳7次不掉入坑中,便能获得奖品。QWER决定参加,但是为了奖品,他提出,参与者能决定什么时候上场。提议被组织者接受之后,QWER现在需要你帮他决定对于每一个场地,他能不能上场赢得游戏。
Output:
对于每个测试实例,如果QWER上场能赢,输出"Yes"(不包括引号),否则输出"No"(不包括引号)。
Sample Input:
15
*.***.*.*.*.*.*
15
***.*..********
Sample Output:
Yes
Yes
解题思路:暴力大法即可解决。由于题目给的字符串最长为100,所以对当前每个字符作为起点i,往后枚举加上步长j后的坐标,同时至少需要7跳才能获奖,所以用tmp(=i+j*k,可以用来判断是否跳出了n(即大于等于n))保存每跳到的点,并判断是否为坑。在起点、步长变化(控制变量)下,进行7次跳,如果跳的过程遇到坑即'.'就退出当前跳的步长,换下一个步长,依次暴力枚举下去,如果flag为true,则可以获奖。
AC代码:
1 #include<bits/stdc++.h>
2 using namespace std;
3 int main()
4 {
5 char a[105];
6 int n,tmp;
7 bool flag;
8 while(cin>>n){
9 cin>>a;
10 flag=false;
11 for(int i=0;i<n-6;++i){ //给出的至少有7个字符
12 if(a[i]=='.')continue; //如果当前字符是坑'.'跳过下面
13 for(int j=1;j<n;++j){ //枚举步长,从1开始枚举
14 for(int k=1;k<=7;++k){ //至少跳7次
15 tmp=i+j*k; //来保存暂时的下标,可以防止越界
16 if(tmp>=n || a[tmp]=='.')break; //如果跳的过程遇到坑或者超过n,退出
17 if(k==7)flag=true; //能跳到7次说明可以获奖
18 }
19 if(flag)break;
20 }
21 if(flag)break;
22 }
23 cout<<(flag?"Yes":"No")<<endl;
24 }
25 return 0;
26 }