描述

现有一两行三列的表格如下：

A B C
D E F

把1、2、3、4、5、6六个数字分别填入A、B、C、D、E、F格子中，每个格子一个数字且各不相同。每种不同的填法称为一种布局。如下：

1 3 5
2 4 6
布局1

2 5 6
4 3 1
布局2

定义α变换如下：把A格中的数字放入B格，把B格中的数字放入E格，把E格中的数字放入D格，把D格中的数字放入A格。
定义β变换如下：把B格中的数字放入C格，把C格中的数字放入F格，把F格中的数字放入E格，把E格中的数字放入B格。

问：对于给定的布局，可否通过有限次的α变换和β变换变成下面的目标布局：

1 2 3
4 5 6
目标布局

输入

本题有多个测例，每行一个，以EOF为输入结束标志。每个测例的输入是1到6这六个数字的一个排列，空格隔开，表示初始布局ABCDEF格中依次填入的数字。

输出

每个输出占一行。可以转换的，打印Yes；不可以转换的，打印No。

输入样例

1 3 5 2 4 6
2 5 6 4 3 1

输出样例

No
Yes

题解

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

// 定义一个布局的结构体，方便下面入队，变换等操作
typedef struct arr {
	int a, b, c, d, e, f;
}arr;
arr s;
queue <arr> q;

int map[654321];
void func1(arr* carr); // α变换
void func2(arr* carr); // β变换
bool hashx(arr x); // 判断布局x是否被搜过
int bfs();

int main()
{
	while (scanf("%d%d%d%d%d%d", &s.a, &s.b, &s.c, &s.d, &s.e, &s.f) != EOF)
	{
		memset(map, 0, sizeof(map));
		// 先将初始布局入队，并标记为1
		q.push(s);
		map[s.f + s.e*10 + s.d * 100 + s.c*1000 + s.b*10000 + s.a*100000 - 123456] = 1;
		if (bfs())
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
		// 最后需要清空队列
		while (!q.empty())
			q.pop();
	}
}

void func1(arr* carr)
{
	swap(carr->a, carr->b);
	swap(carr->a, carr->e);
	swap(carr->a, carr->d);
}

void func2(arr* carr)
{
	swap(carr->b, carr->c);
	swap(carr->b, carr->f);
	swap(carr->b, carr->e);
}

bool hashx(arr x)
{
	int ans = x.f + x.e*10 + x.d * 100 + x.c*1000 + x.b*10000 + x.a*100000 - 123456;
	// 若被没被搜过，标记1，返回true
	if (map[ans] == 0)
	{
		map[ans] = 1;
		return true;
	}
	// 否则返回false
	else
		return false;
}

int bfs()
{
	//当前布局 α布局  β布局
	arr carr, acarr, bcarr;
	while(!q.empty())
	{
		// 如果目标布局被搜过
		if (map[0] == 1)
		{
			return 1;
		}
		// 从队列中取出
		carr = q.front();
		q.pop();
		// α变换
		acarr = carr;
		func1(&acarr);
		// β变换
		bcarr = carr;
		func2(&bcarr);
		// 如果没有被搜过，则入队
		if (hash(acarr))
		{
			q.push(acarr);
		}
		if (hash(bcarr))
		{
			q.push(bcarr);
		}
	}
	// 队列都搜完也没搜到，返回0
	return 0;
}