CQUPT第九届ACM校赛 H 锦鱼突刺 题解

本文主要是介绍CQUPT第九届ACM校赛 H 锦鱼突刺 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目: 

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;
	
}

这篇关于CQUPT第九届ACM校赛 H 锦鱼突刺 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！