蓝桥杯九宫重排（bfs+用set去重）

题目连接

#define _CRT_SECURE_NO_WARNINGS

#include<cstdio>

#include<iostream>

#include<queue>

#include<cmath>

#include<set>

#include<cstring>

using namespace std;

char s[4][4], e[4][4];

char  a[10];

struct point {

	int x, y;

	char status[4][4];

	int cnt = 0;

	point() {

	};

	point(int x, int y, char s[4][4] , int cnt) {

		this->x = x; this->y = y;

		for (int i = 0; i<3; i++)

			for (int j = 0; j<3; j++) {

			this->status[i][j] = s[i][j];

		}

		this->cnt = cnt;

	}

}p;

int ll;

int dx[4] = { 0,1,0,-1 };

int dy[4] = { -1,0,1,0 };

bool is_ok(int x, int y) {

	if (x<0 || x>2 || y<0 || y>2)return false;

	return true;

}

bool check(char(*s)[4], char(*e)[4]) {

	for (int i = 0; i<3; i++)

		for (int j = 0; j<3; j++) {

			if (s[i][j] != e[i][j])return false;

		}

	return true;

}

queue<point>que;

set<int>vis;

bool  change(char (*s)[4]) {

	int ans = 0;

	for (int i = 0; i < 3; i++)

	for(int j=0;j<3;j++){

		if (s[i][j] == '.')ans = ans * 10;

		else ans = ans * 10 + s[i][j] - '0';

	}

	if (vis.count(ans)) //容器中有相同

	{

		return 0;

	}

	vis.insert(ans);//插入容器

	return 1;

}

void bfs() {

	char temp[4][4];

	while (!que.empty()) {

		p = que.front();

		que.pop();

		if (check(p.status,e)) {

			cout << p.cnt << endl;

			return;

		}

		for (int i = 0; i<4; i++) {

			int x = p.x + dx[i];

			int y = p.y + dy[i];

			if (is_ok(x, y)) {

				memcpy(temp, p.status,sizeof(temp));

				temp[p.x][p.y] = temp[x][y];

				temp[x][y] = '.';

				if (change(temp)) {

					que.push(point(x, y, temp, p.cnt + 1));

				}

			}

		}

	}

}

int main() {

	scanf("%s", a);

	int c = 0;

	int dxx, dyy;

	for (int i = 0; i<3; i++)

		for (int j = 0; j<3; j++) {

			if (a[c] == '.') {

				dxx = i, dyy= j;

			}

			s[i][j] = a[c++];

		}

	que.push(point(dxx, dyy, s, 0));

	change(s);

	c = 0;

	scanf("%s", a);

	for (int i = 0; i<3; i++)

		for (int j = 0; j<3; j++) {

			e[i][j] = a[c++];

		}

	bfs();

	return 0;

}

蓝桥杯九宫重排（bfs+用set去重）的相关教程结束。