#pragma warning(disable: 4786)
#include <iostream>
#include <queue>
using namespace std;

// 养成定义宏或const的习惯 方便测试
#define PWDLEN 6
#define STATECODELEN (PWDLEN + 3) * 4

// 注意这里枚举的顺序 把Up和Down放在一起 方便下面的优化
enum Key {Swap0 = 0, Swap1, Up, Down, Left, Right};

// vc中有__int64可用 G++编译不能通过
class State
{
public:
	State(const char *a, int index);
	State(__int64 stateCode);
	bool Press(Key key);
	__int64 StateCode();
	int MemoCode();
	char Depth();
	bool IsInThis(char n);
	bool IsInPos(const State &s);
	char PointedTo();
	bool operator == (const State &rhs);
protected:
	typedef bool (State::*Manipulation)();
	bool PressSwap0();
	bool PressSwap1();
	bool PressUp();
	bool PressDown();
	bool PressLeft();
	bool PressRight();
	void Change();
	void Init();
	void Reset2Code();
private:
	char _a[PWDLEN];

	// 特别注意stateCode是按位操作生成的 借助__int64提高效率
	__int64 _stateCode;
	int _memoCode;
	bool _isChanged;
	char _index;
	char _depth;
	Manipulation _mani[6];
};

class Seacher
{
public:
	Seacher(const char *begin, const char *end);
	~Seacher();
	int Search();
protected:
	int BFS();
private:
	State _begin, _end;
	bool *_memo;
};

int main()
{
	char begin[PWDLEN + 1], end[PWDLEN + 1];
	cin >> begin >> end;
	Seacher s(begin, end);
	cout << s.Search() << endl;
	return 0;
}

State::State(const char *a = NULL, int index = 0) 
: _stateCode(0), _isChanged(true), _index(index), _depth(0)
{
	Init();
	if (a)
	{
		for (int i = 0; i < PWDLEN; ++i)
		{
			_a[i] = a[i] - '0';
		}
	}
}

State::State(__int64 stateCode) 
: _stateCode(0), _isChanged(true), _index(0), _depth(0)
{
	Init();
	__int64 temp;
	temp = stateCode & __int64(0xff);
	_depth = temp;
	stateCode >>= 8;
	temp = stateCode & __int64(0xf);
	_index = temp;
	stateCode >>= 4;
	for (int i = PWDLEN - 1; i >= 0; --i)
	{
		temp = stateCode & __int64(0xf);
		_a[i] = temp;
		stateCode >>= 4;
	}
}

void State::Init()
{
	memset(_a, 0, (PWDLEN + 1) * sizeof(char));
	_mani[Swap0] = &State::PressSwap0;
	_mani[Swap1] = &State::PressSwap1;
	_mani[Up] = &State::PressUp;
	_mani[Down] = &State::PressDown;
	_mani[Left] = &State::PressLeft;
	_mani[Right] = &State::PressRight;
}

bool State::Press(Key key)
{
	// 注意this->*的写法
	return (this->*_mani[key])();
}

inline void State::Reset2Code()
{
	int i, x;
	_memoCode = _index;
	for (i = 0, x = 10; i < PWDLEN; ++i)
	{
		_memoCode += (_a[PWDLEN - 1 - i]) * x;
		x *= 10;
	}
	_stateCode = 0;
	for (i = 0; i < PWDLEN; ++i)
	{
		_stateCode |= _a[i];
		_stateCode <<= 4;
	}
	_stateCode |= _index;
	_stateCode <<= 8;
	_stateCode |= _depth;
}

inline int State::MemoCode()
{
	if (_isChanged)
	{
		Reset2Code();
		_isChanged = false;
	}
	return _memoCode;
}

inline __int64 State::StateCode()
{
	if (_isChanged)
	{
		Reset2Code();
		_isChanged = false;
	}
	return _stateCode;
}

inline char State::Depth()
{
	return _depth;
}

// 用一个函数将_isChanged和_depth
inline void State::Change()
{
	_isChanged = true;
	++_depth;
}

inline bool State::IsInThis(char n)
{
	for (int i = 0; i < PWDLEN; ++i)
	{
		if (_a[i] == n)
		{
			return true;
		}
	}
	return false;
}

inline bool State::IsInPos(const State &s)
{
	return _a[_index] == s._a[s._index];
}

inline char State::PointedTo()
{
	return _a[_index];
}

bool State::PressSwap0()
{
	if (!_index)
	{
		return false;
	}
	char temp = _a[_index];
	_a[_index] = _a[0];
	_a[0] = temp;
	Change();
	return true;
}

bool State::PressSwap1()
{
	if (PWDLEN - 1 == _index)
	{
		return false;
	}
	char temp = _a[_index];
	_a[_index] = _a[PWDLEN - 1];
	_a[PWDLEN - 1] = temp;
	Change();
	return true;
}

bool State::PressUp()
{
	if (9 == _a[_index])
	{
		return false;
	}
	++_a[_index];
	Change();
	return true;
}

bool State::PressDown()
{
	if (!_a[_index])
	{
		return false;
	}
	--_a[_index];
	Change();
	return true;
}

bool State::PressLeft()
{
	if (!_index)
	{
		return false;
	}
	--_index;
	Change();
	return true;
}

bool State::PressRight()
{
	if (PWDLEN - 1 == _index)
	{
		return false;
	}
	++_index;
	Change();
	return true;
}

bool State::operator == (const State &rhs)
{
	return !memcmp(_a, rhs._a, PWDLEN * sizeof(char));
}

Seacher::Seacher(const char *begin, const char *end)
: _begin(begin), _end(end), _memo(NULL)
{
 	int memoLen = 1;
 	for (int i = 0; i < PWDLEN + 1; ++i)
 	{
 		memoLen *= 10;
 	}
 	_memo = new bool[memoLen];
 	memset(_memo, 0, memoLen * sizeof(bool));
}

Seacher::~Seacher()
{
	delete _memo;
	_memo = NULL;
}

inline int Seacher::Search()
{
	return BFS();
}

int Seacher::BFS()
{
	_memo[_begin.MemoCode()] = true;
	queue<__int64> q;
	q.push(_begin.StateCode());
	while (!q.empty())
	{
		State now = q.front();
		if (now == _end)
		{
			return now.Depth();
		}
		q.pop();
		int fbegin = Swap0;
		int fend = Right;

		// 这里表示如果当年指向的点的数没有出现在end中 那么一定要是其成为end的其中一个数
		if (!_end.IsInThis(now.PointedTo()))
		{
			fbegin = Up;
			fend = Down;
		}

		// 注意这里不能加 不能认为当前位置满足要求就不变 考虑swap
// 		if (_end.IsInPos(now))
// 		{
// 			fbegin = Left;
// 			fend = Right;
// 		}
// 		else if (!_end.IsInThis(now.PointedTo()))
// 		{
// 			fbegin = Up;
// 			fend = Down;
// 		}
		for (int key = fbegin; key <= fend; ++key)
		{
			State temp = now;
			if (temp.Press(Key(key)) && !_memo[temp.MemoCode()])
			{
				_memo[temp.MemoCode()] = true;
				q.push(temp.StateCode());
			}
		}
	}
	return 0;
}

• Re:单向BFS + 备忘录 + 一个限界条件 = AC (7) dgsrz 2012-04-05 22:04:34