游客 注册 | 登录
中文 | En

1671 - Chinese Checkers

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB
In chinese checkers a piece can jump must meet two conditions：
1.There is no piece on the Jump-off point and the droppoint.Meanwhile,There is one and only one piece between the two points. 
2.The only piece must be right in the middle of the two points.
For example,from a jump to b('a' is jump-off point,'b' is droppoint,'*' means piece in the position,'.'means no piece in the position).
the cases can jump:        a*b      a..*..b      a.....*.....b
the cases cannot jump:  a**b     a.*..b      a...*.*...b     a.*...b
Now Given a one-dimensional checkerboard,how many times need to jump from a to b(No other movement but jump).

题目输入

The input consists of multiple test cases.Each case contain one line with a character string(length is less than 100),means a one-dimensional checkerboard.'a' is jump-off point,'b' is droppoint,'*' means piece in the position,'.'means no piece in the position.There is only these four character in the string,and there is just one 'a' and one 'b'.There is no piece on the 'a' and 'b' position.

题目输出

For each test case,you should output the least times need to jump from a to b in one line and with one line of output for each line in input.If there is no jump path from a to b,you should output 0. 

输入/输出样例

输入格式

b*.*..*.a
b***.a*..

输出格式

3
0

C语言解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char str[110];
    while(scanf("%s",str) != EOF){
        int loa, lob;
        for(int i = 0;i < strlen(str); i++){
            if(str[i]=='a')loa = i;
            if(str[i]=='b')lob = i;
        }
        int st, en;
        if(loa<lob)st=loa, en=lob;
        else st=lob, en = loa;
        int ans = 0;
        int flag = 1;
        while(st<en && flag){
            int i;
            int offset = 0;
            for(i = st;str[i]!='*';i++)offset++;
            for(int j = 1;j <= offset; j++)if(str[i+j]=='*')flag = 0;
            st = i + offset;
            ans++;
        }
        if(st>en)flag=0;
        flag?printf("%d\n",ans):printf("0\n");
    }
    return 0;
}

C++解答

#include <stdio.h>
#include <string.h>
char s[1000];
int count(int begin,int end)//计算begin到end所需的步数 
{//向左跳再向右跳只能回到原位，所以直接考虑向右跳即可，向右跳的方法最多一种 
	int star,i,x;
	if(begin>=end)
		return 0;
	star=begin;
	while(star<end&&s[star]!='*')//找星号 
		star++;
	if(star*2>begin+end)
		return -9;//中间没有星号，不能到达 
	for(i=star+1;i<=star*2-begin;i++)
		if(s[i]=='*')
			return -9;
	x=count(i-1,end);
	if(x>=0)
		return x+1;
	else
		return -9;
}
void run()
{
	int a=-1,b,n,i;
	n=strlen(s)-1;
	for(i=0;i<=n;i++)//跳的路线是可逆的，所以从a跳到b和从b跳到a等效，只考虑左往右即可 
		if(s[i]=='a'||s[i]=='b')
		{
			if(a==-1)
				a=i;
			else
				b=i;
		}
	i=count(a,b);
	if(i<0) 
		printf("0\n");
	else
		printf("%d\n",i); 
}
int main()
{
	while(scanf("%s",s)!=EOF)
		run();
	return 0;
}
请先登陆