P1379 八数码问题

aoapc上的八数码问题，在luogu上也有类似的题，p1379，经典题目，lrj给出了一个算法，同时给出了三种判重的方法。本来想用std::queue改写一下，但是出了各种问题，只好抄代码ac掉这道题了。。。

#include <bits/stdc++.h>

using namespace std;

typedef int State[9];

const int maxstate = 1000000;

State st[maxstate], goal;

int dist[maxstate];

set<int> vis;

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

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

void init_lookup_table() {vis.clear();}

int try_to_insert(int s) {

	int v = 0;

	for(int i = 0; i < 9; i++) v = v*10+st[s][i];

	if(vis.count(v)) return 0;

	vis.insert(v);

	return 1;

}

int bfs() {

	init_lookup_table();

	int front = 1, rear = 2;

	while(front < rear) {

		State& s = st[front];

		if(memcmp(goal, s, sizeof(s)) == 0) return front;

		int z;

		for(z = 0; z < 9; z++) if(!s[z]) break;

		int x = z/3;

		int y = z%3;

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

			int newx = x + dx[d];

			int newy = y + dy[d];

			int newz = newx * 3 + newy;

			if(newx >= 0 && newy < 3 && newy >= 0 && newy < 3) {

				State& t = st[rear];

				memcpy(&t, &s, sizeof(s));

				t[newz] = 0;

				t[z] = s[newz];

				dist[rear] = dist[front] + 1;

				if(try_to_insert(rear)) rear++;

			}

		}

		front++;

	}

	return 0;

}

int main() {

//	for(int i = 0; i < 9; i++) scanf("%d", &st[1][i]);

	st[1][0] = 2;st[1][1] = 8;st[1][2] = 3;st[1][3] = 1;

	st[1][4] = 9;st[1][5] = 4;st[1][6] = 7;st[1][7] = 6;

	st[1][8] = 5;

	for(int i = 0; i < 9; i++)	scanf("%d", &goal[i]);

	int ans = bfs();

	if(ans > 0) cout << dist[ans];

	else cout << -1 << endl;

	return 0;

}

巴特西

P1379 八数码问题

最新文章

热门文章