1484.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1484 on 2006-06-07 at 11:59:10 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int FN = 128, SN = 2560;
const int DIR[] = { -1, 0, 1 };

int turn[FN][SN], n, p[FN], q[FN];

int walk(int, int);

int main()
{
	int i;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		memset(turn, 0, sizeof(turn));
		for(i = 1; i <= n; i++) scanf("%d", &p[i]);
		for(i = 1; i <= n; i++) { scanf("%d", &q[i]); q[i] = 2*p[i]-q[i]; }
		printf("%d\n", walk(0, 0));
	}
	
	return 0;
}

int walk(int bt, int bo)
{
	int st = 1, i;
	for(i = 1; i <= n; i++)
		if(p[i] != 0) st = st*2*p[i]/__gcd(2*p[i], st);
	memset(turn, -1, sizeof(turn)); turn[bo][bt] = 0;
	queue<int> Q; Q.push((bt<<7)|bo);
	while(!Q.empty()) {
		int s = Q.front(), cst = s>>7, o = s&127; Q.pop();
		for(i = 0; i < 3; i++) {
			int no = o+DIR[i], nst = (cst+1)%st, nt = turn[o][cst]+1;
			if(no == n+1) return nt;
			else if(no < 0 || turn[no][nst] >= 0) continue;
			else if(p[no] != 0 && (cst+1+q[no])%(2*p[no]) < p[no]) continue;
			turn[no][nst] = nt;
			Q.push((nst<<7)|no);
		}
	}
	return 0;
}