蓝桥杯历届试题-九宫重排 （C++代码）

解题思路:
    主要的思路是利用bfs进行广搜，直到搜寻到最终结果，输出路径长度。
注意事项:
    这里需要注意几点与一般的bfs不同的地方。

    1. 对于queue中存储的元素类型，一般的bfs是存储点的坐标，但对于此题来说，每次变化的是九宫图，所以每次要存储对应的字符串序列，但由于还要保存路径长度信息，当然，可以选择hash，我这里采用了更加节省的方法，直接将路径长度和字符串组成一个pair存储起来

    2. 其中涉及到字符串和九宫图的转化，一定要小心

参考代码:

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

int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0 ,0 };
unordered_map<string, bool> Hash;

char** ToMap(string s) {
	char** map = new char*[3];
	for (int i = 0; i < 3; i++) {
		map[i] = new char[3];
	}

	for (int i = 0; i < s.length(); i++) {
		map[i / 3][i % 3] = s[i];
	}

	return map;
}

string ToString(char** map) {
	string s;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			s += map[i][j];
		}
	}
	return s;
}

void Swap(char* a, char* b) {
	char tmp = *a;
	*a = *b;
	*b = tmp;
}

int bfs(string s, string e) {
	queue<pair<string, int>> que;
	que.push(make_pair(s, 0));
	Hash[s] = true;

	while (!que.empty()) {
		pair<string, int> p = que.front(); que.pop();
		string map_s = p.first;
		int dist = p.second;

		if (map_s == e) {
			return dist;
		}

		char** map = ToMap(map_s);
		int index = 0;
		for (int i = 0; i < map_s.length(); i++) {
			if (map_s[i] == '.') {
				index = i;
				break;
			}
		}
		int xx = index / 3;
		int yy = index % 3;
		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx < 0 || nx>2 || ny < 0 || ny>2) {
				continue;
			}
			Swap(&map[xx][yy], &map[nx][ny]);
			string tmpS = ToString(map);
			if (Hash.find(tmpS) != Hash.end()) {
				Swap(&map[xx][yy], &map[nx][ny]);
				continue;
			}
			Hash[tmpS] = true;
			que.push(make_pair(tmpS, dist + 1));
			Swap(&map[xx][yy], &map[nx][ny]);
		}

	}

	return -1;
}


int main() {

	string start, end;
	cin >> start >> end;

	cout << bfs(start, end) << endl;

	return 0;
}