奇数码问题

奇数码问题

你一定玩过八数码游戏，它实际上是在一个 $3×3$ 的网格中进行的，$1$ 个空格和 $1∼8$ 这 $8$ 个数字恰好不重不漏地分布在这 $3×3$ 的网格中。

例如：

1
2
3
5 2 8
1 3 _
4 6 7

在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。

例如在上例中，空格可与左、上、下面的数字交换，分别变成：

1
2
3
5 2 8       5 2 _      5 2 8
1 _ 3       1 3 8      1 3 7
4 6 7       4 6 7      4 6 _

奇数码游戏是它的一个扩展，在一个 $n×n$ 的网格中进行，其中 $n$ 为奇数，$1$ 个空格和 $1∼n^2−1$ 这 $n^2−1$ 个数恰好不重不漏地分布在 $n×n$ 的网格中。

空格移动的规则与八数码游戏相同，实际上，八数码就是一个 $n=3$ 的奇数码游戏。

现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

输入格式

多组数据，对于每组数据：

第 $1$ 行输入一个整数 $n$，$n$ 为奇数。

接下来 $n$ 行每行 $n$ 个整数，表示第一个局面。

再接下来 $n$ 行每行 $n$ 个整数，表示第二个局面。

局面中每个整数都是 $0∼n^2−1$ 之一，其中用 $0$ 代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。

输出格式

对于每组数据，若两个局面可达，输出 TAK，否则输出 NIE。

数据范围

$1≤n<500$

输入样例：

1
2
3
4
5
6
7
8
9
10
3
1 2 3
0 4 6
7 5 8
1 2 3
4 5 6
7 8 0
1
0
0

输出样例：

1
2
TAK
TAK

解析

首先一眼题，很简单的办法便是爆搜，终止条件我们只需要看空格位置是否重合，如果重合我们便与答案局面对照，如果相同则可以到达，不同则继续搜索，最后如果没有符合条件的答案便表示不能到达。

部分代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(x + 1 <= n * n && flag != 1) {
	std::swap(a[x], a[x + 1]);
	dfs(a, x + 1);
	std::swap(a[x], a[x - 1]);
} if(x - 1 >= 1 && flag != 1) {
	std::swap(a[x], a[x - 1]);
	dfs(a, x - 1);	
	std::swap(a[x], a[x + 1]);
} if(x + (n - 1) <= n * n && flag != 1) {
	std::swap(a[x], a[x + (n - 1)]);
	dfs(a, x + (n - 1));	
	std::swap(a[x], a[x - (n - 1)]);
} if(x - (n - 1) >= 1 && flag != 1) {
	std::swap(a[x], a[x - (n - 1)]);
	dfs(a, x - (n - 1));
	std::swap(a[x], a[x + (n - 1)]);
}

很明显这道题并不能用这个，我的爆搜时间复杂度为 $O(n^3)$ ，且这道题还是多道数据

在二维上解决不了，考虑将二维转一维，由题中样例可得转化后的一维图为

1
2
3
4
5
5 2 8
1 3 _
4 6 7

5 2 8 1 3 _ 4 6 7

此样例无法向右交换，但我们可以得到它的其他三种交换后状态 分别为

1
2
3
4
原 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 8 1 3 7 4 6 _

根据向 左 的移动状态可以知道，在空格移动后原数据的相对位置不变，同理 向右也如此。

根据向 上下 的移动状态可以知道，在空格移动后部分原数据的相对位置发生改变，改变的数量为 $n$ 个

从目前是看不出任何东西的，继续思考。此问题为一种 有解性判定 若只考虑输入数列而不考虑结果数列可能并不能得到答案

于是考虑样例

输入局面

1
1 2 3 _ 4 6 7 5 8

结果局面

1
1 2 3 4 5 6 7 8 _

易得，想要从输入局面到结果局面 将空格先向右交换然后向下交换，最后再向右交换

分别为

1
2
3
1 2 3 4 _ 6 7 5 8
1 2 3 4 5 6 7 _ 8
1 2 3 4 5 6 7 8 _

空格对数的交换对数列造成了哪些影响？左右交换是改变了一个数的位置，但对一整段数列而言这一个数的相对位置并没有改变，而上下交换却影响的 $n$ 个数的相对位置，有什么办法能快速记录这 $n$ 个数的影响吗？我们发现，根据题意整段数列不存在相同的数，于是我们可以通过记录 逆序对 的方法，来记录这 $n$ 个数的影响。

比如

1
2
3
1 2 3 4 _ 6 7 5 8 改变的逆序对个数为 0
1 2 3 4 5 6 7 _ 8 改变的逆序对个数为 -2
1 2 3 4 5 6 7 8 _ 改变的逆序对个数为 0

可以发现，左右移动不会使逆序对的个数改变，而上下移动会对逆序对的个数改变，因为数列的长度始终为奇数，所以空格每次交换，在数列上的表现一定是移动奇数个单位，从而使 $n - 1$ 个数与空格交换的数的相对位置发生改变。

因此，我们就可以将这 $n$ 个数的各种情况举例出来，看是否存在某种规律。跟上面同理，我们将一段 $n = 3$ 的数列的空格向上移动，就有

1
2
3
4
5
6
7
8
9
10
11
a b c d e _ g h i
c d e _
_ d e c

前面是数列各数的关系，后面是逆序对改变前和改变后的数量
c > d > e 0 2
c > e > d 2 0
d > c > e 2 2
d > e > c 1 3
e > d > c 0 2 
e > c > d 1 1

我们发现，除了两个逆序对相等的情况，其他都改变了 2 个。

同样我们也可以推出 $n = 5$ 的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
q w e r t
y u i o p
a s _ f g
h j k l z
x c v b n

q w e r t y u i o p a s _ f g h j k l z x c v b n 原
q w e r t y u i o p a _ s f g h j k l z x c v b n 左
q w e r t y u i o p a s f _ g h j k l z x c v b n 右
q w e r t y u _ o p a s i f g h j k l z x c v b n 上

向上移动，部分变成了
o p a s i
i o p a s

前面是数列各数的关系，后面是逆序对改变前和改变后的数量
i > o > p > a > s 6 10
i > o > p > s > a 5 9
i > o > a > p > s 5 9
i > o > a > s > p 4 8
i > o > s > a > p 3 7
i > o > s > p > a 4 8
（因为太多 只列举部分，但这个部分可能会产生误导）
（从这里可能会误导，|结果数列的逆序对数量-输入数列的逆序对数量| = n - 1，所以我特地找了个数据）
a > p > o > i > s 6 4

可以发现，每次向上（下）移动后逆序对的个数改变都为偶数个，因为我们将空格移动后，将会改变奇数个数的相对位置，但若看成将某个数移动到空格的位置上，就相当于这个数与前面 $n - 1$ 个数交换了位置，因为 $n - 1$ 为偶数，所以逆序对的变化也一定为偶数，为什么？看 $n = 3$ 时举的例子，同样，当 $n > 3 且 n\mod 2≠0$ 时，都可以简化为 $n = 3$ 的情况

因此我们可以得到，向左右移动时，数列的逆序对数量不变，向上下移动时，数列的逆序对奇偶性不变，若结果数列的逆序对个数的奇偶性与输入数列的逆序对个数的奇偶性相同，则说明可以到达，反之则不能，这句话也可以换个意思，由我们模拟的样例可以得到，假如想要从结果数列到达输入数列，**那么必定可以得到 |结果数列的逆序对个数 - 输入数列的逆序对个数| Mod 2 = 0 **，于是我们只需要得到这两个数列的逆序对个数就可以得到我们最终的答案。

最后要注意逆序对的个数要开long long，最坏情况为递减数列，即最大逆序对的个数为 $2n^2$ 即为 $250000^2$ 会爆int（但此题的数据并没有卡这个）

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <iostream>

const int MAXN = 500 * 500 + 5;
int arr[MAXN], brr[MAXN], b[MAXN];

long long cnt = 0;
void mergeSort(int a[MAXN], int l, int mid, int r) {
	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++) {
		if(j > r || i <= mid && a[i] <= a[j]) b[k] = a[i++];
		else b[k] = a[j++], cnt += mid - i + 1;
	} for (int k = l; k <= r; k++) a[k] = b[k];
}

void merge(int l, int r, int a[MAXN]) {
	if(l < r) {
		int mid = (l + r) >> 1;
		merge(l, mid, a);
		merge(mid + 1, r, a);
		mergeSort(a, l, mid, r);
	}
}

int main() {
	int n;
	while(scanf("%d", &n) != EOF) { //多组数据的输入方式
		int kx = 0, ky = 0;
		for (int i = 1; i <= n * n; i++) {
			int x = 0;
			scanf("%d", &x);
			if(x != 0) arr[++kx] = x;
		}
		for (int i = 1; i <= n * n; i++) {
			int x = 0;
			scanf("%d", &x);
			if(x != 0) brr[++ky] = x;
		}
		
		if(n == 1) { puts("TAK"); continue; }
		
		long long ans_arr = 0, ans_brr = 0;
		merge(1, kx, arr);
		ans_arr = cnt, cnt = 0;
		merge(1, ky, brr);
		ans_brr = cnt, cnt = 0;
		
		if((ans_arr & 1) != (ans_brr & 1)) puts("NIE");
		else if(std::abs(ans_brr - ans_arr) % 2 == 0) puts("TAK");
		else puts("NIE");
	} return 0;
}
算法
算法 逆序对 归并排序 有解性判定

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！