C/C++教程

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 锦鱼突刺 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!