题目:
Description
CC公主被抓走了，为了救回她，你要通过九个关卡的考验。
在这一关中，你要通过一座浮桥。浮桥由多块漂浮的木板组成。不幸的是，水里生存着一种凶残的锦鱼，锦鱼的突刺会刺穿木板，如果你走到被刺穿的木板上，那么你就会掉进水里，然而你并不会游泳。幸好你学会了跳跃技能，可以跳过多块木板。
请问你最少要跳多少次，才能在不掉进水里的情况下到达对岸？
Input
输入的第一行包含一个正整数T(1<=T<=100)。T表示数据组数。
每一组数据的第一行包括两个整数L(1<=N<=1000)和M(1<=M<=1000)。L表示木板的个数。M表示一次跳跃你可以跳过的木板的个数。接下来一行包括一个长度为L的字符串，从左边数起，字符串的第i位为“O”表示第i个木板是完好的，为“X”表示第i个木板是被刺穿的。
一开始你站在第1个木板上，你的终点是第N个木板。
数据保证第1个木板和第N个木板是完好的。
Output
对于每组数据，如果可以抵达终点，在单独的一行中输出一个整数表示到达终点所需的最少跳跃次数。如果无法抵达终点，在单独的一行中输出“-1”。
Sample Input
4
3 1
OXO
3 2
OXO
9 3
OOOXOXOOO
6 2
OXOOXO
Sample Output
1
-1
1
2
HINT
对于第一个样例，你可以从第1个木板跳到第3个木板。
对于第二个样例，你无法抵达终点。
对于第三个样例，你可以走到第3个木板，然后跳到第7个木板，最后走到第9个木板。
对于第四个样例，你可以跳到第4个木板，然后走到第3个木板，最后跳到第6个木板。
我的想法与思路： 我通过对于字符串的处理来分割所有的可走路段和不可走路段，然后从第一个可走的路段向最后一个可走的路段搜索并用MIN记录最小值，可跳到第N个路段的判断方式是判断DUMP值处于两个路段中间的所有格子数 和 两个路段直接的所有格子数加两个路段自身的长度，处于这个区间便可以跳跃。
因为1<=N<=1000,所以最多拥有500个可走路段，纯搜索会存在很多不必要的判断，应为有可能DUMP已经远远小于我们记录的路段长度，但dfs依然在遍历后面的路段是否可以跳，所以我们可以进行优化，if ( num > dump )，则跳出搜索。
#include<iostream>
#include<string.h>
#include<string>
using namespace std;
int roads[1005];
int za[1005];
int road_num = 0;
int za_num = 0;
int len,dump;
int MIN = __INT32_MAX__;//记录最小值
void dfs( int now , int end , int dump_num ){
if ( now == end && dump_num < MIN)//找到末尾并记录
MIN = dump_num;
int num = 0;
for ( int k = now + 1 ; k <= end ; k++ ){
if ( num > dump )
return;
num += roads[ k ];
num += za[ k-1 ];
if ( num + roads[now] >= dump && dump >= num - roads[k] )//如果可以跳到第K个路段，就跳跃并继续搜索
dfs( k , end , dump_num + 1 );
}
return;
}
int main(){
int n;cin>>n;
while( n-- ){
cin>>len>>dump;
MIN = __INT32_MAX__;
memset( za , 0 , sizeof za );
memset( roads , 0 , sizeof roads );
road_num = 0;
za_num = 0;
string road;
cin>>road;
char Now = road[0];
while( road.length() != 0){
for ( int k = 0 ; k < road.length() ; k++ ){
if ( k == road.length() - 1 && road[k] == Now ){
Now=='O'?roads[road_num++] = k + 1:za[za_num++] = k + 1;
road = "";
break;
}
if ( road[k] != Now ){
if ( Now == 'O' ){
roads[road_num++] = k;Now ='X';
}else{
za[za_num++] = k;Now='O';
}
road = road.substr( k );
break;
}
}
}//分割所有的障碍物和可走的路段
dfs( 0 , road_num - 1 , 0);//从路段0向最后一段路进行搜索
if ( MIN == __INT32_MAX__ )
MIN = -1;
cout<<MIN<<endl;
}
return 0;
}