洛谷P1379 八数码难题【A-star】

P1379 八数码难题

八数码难题首先要进行有解性判定，避免无解情况下盲目搜索浪费时间。

有解性判定

P10454 奇数码问题

题意简述

在一个 $n\times n$ 的网格中进行，其中 $n$ 为奇数，$1$ 个空格和 $[1,n^2-1]$ 这 $n^2-1$ 个数不重不漏地分布在网格中。空格可与上下左右的数字交换位置。现给定两个奇数码游戏的局面，判定是否存在一种移动空格的方式使得互相可达。

实际上，八数码问题就是一个 $n=3$ 的奇数码游戏。

思路

将网格图转为长为 $n^2-1$ 的一维序列，例如：

5 2 8
1 3 _
4 6 7

可记为 $5,2,8,1,3,4,6,7$ ，忽略空格。可以发现：若左右移动空格，该序列不变；若上下移动空格，例如：

5 2 _
1 3 8
4 6 7

序列变为 $5,2,1,3,8,4,6,7$ ，相当于把 $8$ 往前移动了 $n-1=2$ 位，有两个数字到了 $8$ 的后面，那么这两个数字中，原来与 $8$ 形成逆序对的变成了非逆序对，原来与 $8$ 形成非逆序对的变成了逆序对。

进一步思考：

1.若在位置发生变动的数中原有奇数个逆序对，由于 $n-1$ 是偶数，那么原来也有奇数个非逆序对，因此交换后逆序对的个数仍为奇数；

2.若在位置发生变动的数中原有偶数个逆序对，由于 $n-1$ 是偶数，那么原来也有偶数个非逆序对，因此交换后逆序对的个数仍为偶数。

综上所述，无论怎么交换，逆序对个数的奇偶性不变，因此可以比较初状态和末状态的逆序对（用树状数组统计）奇偶性是否相同，方可判定是否有解。

代码实现

注意 $0$ 不参与统计，忘了这一点会 WA。

#include <bits/stdc++.h>

using namespace std;

int n;

int lowbit(int p){return p & (-p);}

void insert(int p,int x,vector <int>& c){
	for(;p <= n;p += lowbit(p))
		c[p] += x;
} 

int query(int p,vector <int>& c){
	int sum = 0;
	for(;p;p -= lowbit(p)) 
		sum += c[p];
	return sum;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(cin >> n){
		n = n * n; 
		vector <int> c(n + 1,0);
		int x,ans1,ans2,cnt1,cnt2;
		cnt1 = cnt2 = ans1 = ans2 = 0;
		for(int i = 1;i <= n;i++){
			cin >> x;
			if(!x) continue;
			cnt1++;
			insert(x,1,c);
			ans1 += cnt1 - query(x,c);
		}
		for(int i = 0;i <= n;i++) c[i] = 0;
		for(int i = 1;i <= n;i++){
			cin >> x;
			if(!x) continue;
			cnt2++; 
			insert(x,1,c);
			ans2 += cnt2 - query(x,c);
		}	
		if(ans1 % 2){
			if(ans2 % 2) cout << "TAK" << endl;
			else cout << "NIE" << endl;
		}else{
			if(ans2 % 2) cout << "NIE" << endl;
			else cout << "TAK" << endl;
		}
	}
	return 0;
}

A-star

其实本题不需要可行性判定，但学一下也无妨。

设计估价函数 $h(state)$ 表示当前状态所有数字与其目标位置的曼哈顿距离和，即：
$$h(state)=\sum _{i=1}^8\left|x_i-x_{target}\right|+\left|y_i-y_{target}\right|$$
显然实际操作数 $g(state)\ge h(state)$ ，因为 $h$ 表示每个数字去目标点都走最短路，而实际至少得走这么远，$h$ 函数可采纳且较接近真实值（相比之下“错位数”，即不在目标位置的数字个数，这一估价函数虽可采纳但大多数时候远小于真实值，求解效率低），最终入队的总代价即为 $f=g+h$ 。

代码实现

#include <bits/stdc++.h>

using namespace std;

const string TARGET = "123804765";
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};

struct Node{
	string state;
	int g,h,f;
	
	Node(string s,int _g,int _h) :
		state(s),g(_g),h(_h),f(_g + _h) {}
	
	//重载运算符
	bool operator < (const Node& other) const {
		return f > other.f;
	} 
};

//预处理target状态坐标
void initTargetPos(unordered_map <char,int>& pos_map){
	for(int i = 0;i < 9;i++){
		char c = TARGET[i];
		if(c != '0') pos_map[c] = i;
	}
} 

//函数求曼哈顿距离和 
int mahattan(const string& state,const unordered_map <char,int>& pos_map){
	int distance = 0;
	for(int i = 0;i < 9;i++){
		char c = state[i];
		if(c == '0') continue;
		int target_pos = pos_map.at(c);
		//当前数字坐标 
		int cur_x = i % 3;
		int cur_y = i / 3;
		//目标位置坐标 
		int tar_x = target_pos % 3;
		int tar_y = target_pos / 3;
		distance += abs(cur_x - tar_x) + abs(cur_y - tar_y);
	}
	return distance;
}

int A_star(string start){
	if(start == TARGET) return 0;
	//预处理目标位置 
	unordered_map <char,int> pos_map;
	initTargetPos(pos_map);
	priority_queue <Node> open_list;
	unordered_map <string,int> min_cost;
	int start_h = mahattan(start,pos_map);
	open_list.push(Node(start,0,start_h));
	min_cost[start] = 0;
	while(!open_list.empty()){
		Node cur = open_list.top();
		open_list.pop();
		string state = cur.state;
		if(state == TARGET) return cur.g;
		//非最优路径则跳过
		if(min_cost[state] < cur.g) continue;
		//找出0的位置 
		int pos = state.find('0');
		int x = pos % 3;
		int y = pos / 3;
		for(int i = 0;i < 4;i++){
			int tx = x + dx[i];
			int ty = y + dy[i];
			//越界 
			if(tx < 0 || tx >= 3 || ty < 0 || ty >= 3) continue;
			//0的新坐标 
			int new_pos = tx + ty * 3;
			string new_state = state;
			swap(new_state[pos],new_state[new_pos]);
			int new_g = cur.g + 1;
			//未曾入队或有更优解 
			if(min_cost.find(new_state) == min_cost.end() || new_g < min_cost[new_state]){
				min_cost[new_state] = new_g;
				int new_h = mahattan(new_state,pos_map);
				open_list.push(Node(new_state,new_g,new_h));
			} 
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string start;
	cin >> start;
	cout << A_star(start) << endl;
	return 0;
}