hdu1195 Open the Lock

双向广搜的没写，这个是普通bfs，哪天改一下……

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

int T, vis[10000];
string st, en;
int dir[2] = {-1, 1};
typedef struct {
	string a;
	int ans;
}Node;

string op(string s, int i, int add)
{
	s[i] += add;
	if (s[i] < '1')
		s[i] = '9';
	else if (s[i] > '9')
		s[i] = '1';
		
	return s;
}

void bfs()
{
	queue<Node> q;
	Node n0;
	
	n0.a= st, n0.ans = 0;
	q.push(n0);
	while (!q.empty())
	{
		Node n1 = q.front(), n2;
		q.pop();
		if (n1.a == en)
		{
			cout << n1.ans << endl;
			return;
		}
		n2 = n1;
		for (int i = 0; i < 4; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				n2.a = op(n1.a, i, dir[j]);
				if (vis[stoi(n2.a)])
					continue;
				vis[stoi(n2.a)] = 1;
				n2.ans = n1.ans + 1;
				q.push(n2);
			}
		}
		for (int i = 0; i < 3; i++)
		{
			n2 = n1;
			swap(n2.a[i], n2.a[i + 1]);
			if (vis[stoi(n2.a)])
				continue;
			vis[stoi(n2.a)] = 1;
			n2.ans++;	
			q.push(n2);
		}
	}
}

int main()
{
	cin >> T;
	while (T--)
	{
		memset(vis, 0, sizeof(vis));
		cin >> st >> en;
		bfs();
	}
	
	return 0;
}