snakes and ladders

蛇和梯子的游戏。网上还木有这个题。…………

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stdlib.h>
using namespace std;


bool visitFlag[10001]; //该位置是否到达过
int snakeFlag[10001]; //此处是否有蛇头
int ladderFlag[10001]; //此处是否有梯子
int end;


//用滚动数组
int bfs(queue<int> q[2])
{
	int a = 0, b = 1;
	int step = 0;
	while (!q[a].empty())
	{
		swap(a, b);
		step++; //当前步数加1
		while (!q[b].empty())
		{
			int cur = q[b].front();
			q[b].pop();
			if (cur == end)
				return step - 1;


			for (int i = 1; i <= 6; i++)
			{
				if (cur + i == end)
					return step;
				if (cur + i <= end && !visitFlag[cur+i])
				{
					//无论是到蛇头，或是梯子处，都等于同时访问了两处
					int temp = snakeFlag[cur + i];
					if(temp > 0 && !visitFlag[temp]){
						if(temp == end)
							return step;
						visitFlag[temp] = true;
						q[a].push(temp);
					}else{
						temp = ladderFlag[cur + i];
						if(temp > 0 && !visitFlag[temp]){
							if(temp == end)
								return step;
							visitFlag[temp] = true;
							q[a].push(temp);
						}else{
							q[a].push(cur + i);


						}
					}
					visitFlag[cur + i] = true;
				}
			}
		}
	}


	return 0;
}


int main()
{
	int k;
	cin >> k;
	int N, S, L;


	while (k--)
	{
		scanf("%d %d %d", &N, &S, &L);
		int a, b;
		end = N * N;
		memset(visitFlag, 0, sizeof(visitFlag));
		memset(snakeFlag, 0, sizeof(snakeFlag));
		memset(ladderFlag, 0, sizeof(ladderFlag) );


		for (int i = 0; i < S; i++)
		{
			cin >> a >> b;
			snakeFlag[a] = b;
		}


		for (int i = 0; i < L; i++)
		{
			cin >> a >> b;
			ladderFlag[a] = b;
		}


		queue<int> q[2];
		q[0].push(1);
		cout << bfs(q) << endl;
		system("pause");
	}
	return 0;
}