a.cpp

ACM大赛基本练习题

#include <stdio.h>

#define MAXD 25
#define MAXN 55
#define INF 32768

char board[MAXN];
int minStep[MAXN];
int d[MAXN];
int n, dn;

void read_dat()
{
	int i;

	scanf( "%d", &n );
	scanf( "%s", board );
	scanf( "%d", &dn );
	dn *= 2;

	for( i = 0; i < dn; i+=2 )
	{
		scanf( "%d", &d[i] );
		d[i + 1] = -d[i];
	}

	for( i = 0; i < n; ++i )
		minStep[i] = INF;
}

void make_it()
{
	int q[MAXN];
	int top = 0, tail = 0;
	int i, p;

	q[0] = 0;
	minStep[0] = 0;

	while( tail <= top )
	{
		for( i = 0; i < dn; ++i )
		{
			p = q[tail] + d[i];
			if( p >= 0 && p < n && board[p] != 'o' && minStep[p] == INF )
			{
				minStep[p] = minStep[ q[tail] ] + 1;
				q[ ++top ] = p;
				if( p == n - 1 )
					return;
			}
		}
		++tail;
	}
}

int main()
{
	int i, testCase;

	scanf( "%d", &testCase );

	for( i = 0; i < testCase; ++i )
	{
		read_dat();
		make_it();
		if( minStep[n - 1] == INF )
			printf( "-1\n" );
		else
			printf( "%d\n", minStep[n - 1] );
	}

	return 0;
}