<Java>26 算法入门
本文最后更新于：2023年9月9日 下午
26 算法初级
26.1 算法的执行时间
度量一个算法执行时间的方法：
-
事后统计方法
该方法可行，但需要实际运行该程序，并且结果受环境因素影响。
-
事前估算方法
通过分析算法的时间复杂度来判断哪个算法更优
#时间频度
算法花费的时间与算法中语句的执行次数成正相关。算法中语句执行次数越多，其花费时间也就越多。
一个算法中的语句执行次数称为 时间频度（语句频度），记为 T(n)
举例说明（计算 1 - 100 内所有整数之和）：
-
方法一：
int result = 0; int n = 100; for (int i = 1; i <= n; i++) { result += i; }该方法执行了 100 次计算，因此其时间复杂度 T(n) = n
-
方法二：
int result; result = (1 + n) * (n / 2);该方法执行了 1 次计算，因此其时间复杂度 T(n) = 1
26.1.1 时间复杂度
一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用 T(n) 表示。
若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称 f(n) 为 T(n) 的同量级函数。记作：T(n) = O(f(n))。
称 O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
如：T(3n2+2n-1) 的时间复杂度为 O(n2)
常见的时间复杂度（从小到大排列）：
- 常数阶 O(1)
- 对数阶 O(㏒kn)
- 线性阶 O(n)
- 线性对数阶 O(n㏒kn)
- 平方阶 O(n2)
- 立方阶 O(n3)
- k 次方阶 O(nk)
- 指数阶 O(2n)
计算时间复杂度的方法：
- 用常数 1 代替运行时间中的加法常数
- 修改后的运行次数函数中，只保留最高阶项
- 去除最高阶项的系数
平均时间复杂度、最坏时间复杂度：
-
平均时间复杂度：指所有可能的输入实例以等概率出现的情况下，该算法的运行时间
-
最坏时间复杂度：最坏情况下的时间复杂度。
一般讨论时间复杂度都是讨论最坏时间复杂度。原因是：最坏时间复杂度是算法在任何输入实例上运行时间的界限。这就保证了算法运行时间不会比最坏情况更长。
最坏时间复杂度和平均时间复杂度也许不一致。这和具体算法有关。
#算法的空间复杂度
类似于时间复杂度的讨论，一个算法的空间复杂度定义为该算法所耗费的存储空间。它也是问题规模 n 的函数。
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与问题规模 n 相关。
在做算法分析时，主要讨论的是时间复杂度。从用户体验上看，更看重程序执行的速度。一些缓存产品和算法本质是用空间换时间。
26.2 常用的算法
26.2.1 二分查找算法
二分查找只适用于从有序数列中进行查找。其运行时间为 O(㏒2n)
——二分查找，见 [5.3.2 二分查找]
#一个用到二分查找算法的典型题目
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
题解：
注意到，随着 k 的增加，吃光香蕉的用时 t 随之减少。取食数量 k 与进食总时间 t 呈线性相关。
因此，可以使用二分查找算法，找出 t == h 时，k 的最小取值
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int max = 0; // k 可能取到的最大值。该值等于：香蕉堆中香蕉数量的最大值
int min = 0; // k 可能取到的最小值。该值等于：香蕉总数 / 规定时间
long sum = 0; // 香蕉总数
/* 进行一次遍历，完成对 max、min、sum 的初始化 */
for (int n : piles) {
sum += n;
if (max < n) max = n;
}
/* 由于每堆香蕉至少需要 1 小时，当 piles.length == h 时，k 是那个香蕉堆最大值 */
if (piles.length == h) return max;
min = (sum + h - 1) / h; // 这里是 int 除法的向上取整
/* 二分查找，如果在 p 情况下超时（吃不完香蕉），说明 k > p
如果在 p 情况下提前吃完，说明 k < p
如果恰好吃完，由于要求返回那个最小 k 值，我们仍要在 < p 的范围内查找 */
int p = min;
while (max >= min) {
p = (max + min) / 2;
if (check(piles, p) <= h) max = p - 1;
else min = p + 1;
}
return min;
}
/* 计算在吃 n 根的情况下，需要用时多久吃完 */
private long check(int[] piles, int n) {
long ret = 0;
for (int i : piles) {
ret += (i + n - 1) / n;
}
return ret;
}
}26.2.2 分治算法
分治算法是一种重要算法。其核心思想是 分而治之。
将一个复杂问题分为多个子问题，再将子问题分为更小的子问题。直到那些子问题都能简单地直接得解，原问题的解即子问题解的组合。
该算法也是很多高效算法的基础，如排序算法（快速排序、归并排序），傅立叶变换（快速傅立叶变换）等。
26.2.3 动态规划
动态规划的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解
与分治法不同的是，适用于动态规划求解的问题，其分解得到的子问题往往不是互相独立的。下一子阶段的求解往往是建立在上一子阶段解的基础上的。
#一个用到动态规划的典型题目：
给你两个整数
m和n，分别表示一块矩形木块的高和宽。同时给你一个二维整数数组prices，其中prices[i] = [hi, wi, pricei]表示你可以以pricei元的价格卖一块高为hi宽为wi的矩形木块。每一次操作中，你必须按下述方式之一执行切割操作，以得到两块更小的矩形木块：
- 沿垂直方向按高度 完全 切割木块，或
- 沿水平方向按宽度 完全 切割木块
在将一块木块切成若干小木块后，你可以根据
prices卖木块。你可以卖多块同样尺寸的木块。你不需要将所有小木块都卖出去。你 不能 旋转切好后木块的高和宽。请你返回切割一块大小为
m x n的木块后，能得到的 最多 钱数。注意你可以切割木块任意次。
题解：
我们可以模拟切分木块的过程，从而得到答案。
对于任意木块 m × n，我们可以将其切开。此时该木块的价值 V 等于两个子木块的价值和。具体来说：
- 沿横向切开时，木块价值 V(m, n) = V(i, n) + V(m - i, n)
- 沿纵向切开时，木块价值 V(m, n) = V(m, i) + V(m, n - i)
- 也可以选择不切开，此时木块价值为 prices(m, n)
一块木块的价值是上述三种情况中的最大值。
我们可以维护一个数组，从最小木块开始统计那些木块的价值。直到统计到最大木块时，那个值即是答案。
class Solution {
public long sellingWood(int m, int n, int[][] prices) {
/* 将那些不分割的情况记录 */
long[][] val = new long[m + 1][n + 1];
for (int[] ints : prices) val[ints[0]][ints[1]] = ints[2];
/* 最小的高度开始，统计木块价值 */
for (int i = 1; i <= m; i++) {
/* 从最小的宽度开始，统计木块的价值 */
for (int j = 1; j <= n; j++) {
/* 在该高度纵切 */
for (int k = 1; k <= j - k; k++) {
long temp = val[i][k] + val[i][j - k];
if (temp > val[i][j]) val[i][j] = temp;
}
/* 在该宽度横切 */
for (int u = 1; u <= i - u; u++) {
long temp = val[i - u][j] + val[u][j];
if (temp > val[i][j]) val[i][j] = temp;
}
}
}
return val[m][n];
}
}26.2.4 KMP 算法
KMP（Knuth-Morris-Pratt，字符串查找算法），该算法以提出该算法的三人姓名命名，是一个解决查找 模式字符串 在 文本中 出现位置的经典算法。
KMP 算法利用前面判断过的信息，通过一个 next 数组（部分搜索池），保存模式串中，前后最长公共子序列的长度。每次回溯时，通过 next 数组找到前面匹配过的位置，省去了大量计算时间。
在 KMP 算法里，源串指针永远不会向前回溯，而对象串指针在当前位置匹配成功时后移，匹配失败时前移。
KMP 算法步骤
见 labuladong 大佬写的：KMP 算法详解 - 知乎
实现 KMP 算法
class KMP {
private char[] ps = null;
private int[][] next = null; // 状态转移表，即“有限状态自动机”
/* 初始化，包括初始化部分匹配池 */
public KMP(String pat) {
ps = pat.toCharArray();
next = new int[ps.length][256];
next[0][ps[0]] = 1;
for (int j = 1, x = 0; j < ps.length; j++) { // 当前状态位置 j，影子状态位置 x
for (int c = 0; c < 256; c++) {
if (c == ps[j]) next[j][c] = j+1; // 匹配时，状态推进
else next[j][c] = next[x][c]; // 不匹配时，状态回退。那个回退位置已由影子状态决定
}
x = next[x][ps[j]];
}
}
/* 匹配对象字符串 */
public int search(String txt) {
char[] ts = txt.toCharArray();
for (int tp = 0, np = 0; ; tp++) { // 源串指针 tp，对象串指针 np
if (np >= next.length) return tp - next.length; // 对象串指针指向对象串末尾时，即匹配成功
else if (tp >= ts.length) return -1;
/* 根据部分匹配池的指示，进行状态转移
具体来讲，当 os[tp]=ts[np]（匹配成功）时，状态推进。否则，状态回退 */
np = next[np][ts[tp]];
}
}
}上述算法的时间复杂度是
优化 KMP 算法
所有字符中，能实现状态推进的字符只有一个，该字符就是匹配字符。对于其他字符，状态回退到的位置由影子状态决定。
不记录状态转移，而只记录每个当前状态的影子状态，也能实现 KMP 算法。
这样一来，优化了内存空间，也能适配更大的字符集。
class KMP {
private char[] ps = null;
private int[] shadow = null; // 影子位置表，即“模式匹配串”
/* 初始化，包括初始化部分匹配池 */
public KMP(String pat) {
ps = pat.toCharArray();
shadow = new int[ps.length];
shadow[0] = -1;
for (int j = 1, x = 0; j < ps.length; j++) { // 当前状态位置 j，影子状态位置 x
shadow[j] = x;
while (true) {
if (x < 0 || ps[x] == ps[j]) { // 满足条件时，影子状态推进。
x++;
break;
} else x = shadow[x]; // 否则，查询影子状态
}
}
}
/* 匹配对象字符串 */
public int search(String txt) {
char[] ts = txt.toCharArray();
for (int tp = 0, np = 0; ; tp++) { // 源串指针 tp，对象串指针 np
if (np >= ps.length) return tp - ps.length; // 对象串指针指向对象串末尾时，即匹配成功
else if (tp >= ts.length) return -1;
while (true) {
if (np < 0 || ps[np] == ts[tp]) { // 满足条件时，状态推进。
np++;
break;
} else np = shadow[np]; // 否则，查询影子状态
}
}
}
}上述算法的时间复杂度是
26.2.5 贪心算法
贪心算法（贪婪算法）是指在对问题进行求解时，在每一步选择中都采取最好或最优的选择。从而希望结果是最好或最优的算法。
贪婪算法得到的结果不一定是最优结果，但都是相对接近最优的结果。
——一个贪心算法的例子，见本章附录：[骑士周游问题]
26.2.6 普里姆算法
最小生成树问题（MST，Minimum Cost Spanning Tree）：给定一个带权的无向连通图，如何选取一棵生成树，时树上所有边的权总和最小。
要解决最小生成树问题，可以采取 普里姆算法（Prim）
#普里姆算法步骤：
示范一个联通网图的格式。后面算法中的 int[][] map 都是该格式的联通网：
int[][] map = new int[][]{
{0, 1, 2, 4, 5},
{1, 0, 3, 0, 0},
{2, 3, 0, 6, 0},
{4, 0, 6, 0, 7},
{5, 0, 0, 7, 0}};
int n = map.length;网点编号为 [0, n)，n 为网点数量。map[a][b] 是网点 a 与网点 b 间路径的权（0 为不连通）
graph LR
A((0))--1---B((1))
A--2---C((2))
B--3---C
A--4---D((3))--6---C
A--5---E((4))--7---D- 从任意顶点 i（0 <= i < n）起构造最小生成树。将该顶点标记为已访问
- 如果联通网图中存在剩余顶点，则记录那些与已访问顶点相连的边中，权值最小的边（避免产生回路），并将该顶点加入已访问集合。
- 联通网图中没有未访问节点时，即所有顶点都被联通
#实现普里姆算法
public static int[][] prim(int[][] map) {
/* 初始化 */
Set<Integer> visited = new HashSet<>(); // 已访问集合
Set<Integer> remain = new HashSet<>(); // 待访问集合
int n = map.length; // 网点数量
int[][] ret = new int[n][n]; // 极小联通子图
for (int i = 1; i < n; i++) remain.add(i);
visited.add(0);
/* 记录待访问集合与已访问集合的节点间，权值最小的边，并将该节点加入已访问集合 */
while (!remain.isEmpty()) {
int min = 0;
int point = -1;
for (Integer i : visited) {
for (Integer j : remain) {
int current = map[i][j];
if (current != 0 && (min == 0 || current < min)) {
min = current;
point = j;
}
}
}
visited.add(point);
remain.remove((Integer) point);
ret[y][x] = min;
ret[x][y] = min;
}
return ret;
}26.2.7 克鲁斯卡尔算法
解决最小生成树问题的另一种方法是 克鲁斯卡尔算法（Kruskal）
#克鲁斯卡尔算法步骤
- 构建一个只含 n 个节点的森林。
- 依照权值从小到大，从联通网中选择边加入森林（避免产生回路）。
- 直到森林变成一棵树为止，就完成了最小生成树
#实现克鲁斯卡尔算法
public static int[][] kruskal(int[][] map) {
/* 节点类（局部内部类） */
class Node{
Node prev = null;
Node getSuper() {
if (prev == null) return this;
else return prev.getSuper();
}
}
int n = map.length;
/* 构建一个只含 n 个节点的森林 */
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) nodes[i] = new Node();
int[][] ret = new int[n][n];
/* 将所有边进行初始化。将这些边加入一个优先级队列，以便从小到大取出
对于其中每一项 i 都有：i[0] 为权值，i[1]、i[2] 为该边连接的两个节点 */
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(o -> o[0]));
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int temp = map[i][j];
if (temp != 0) pq.add(new int[]{temp, i, j});
}
}
/* 依照权值从小到大，从联通网中选择边加入森林
取出边时，通过比较两个顶点的顶级父节点是否相同，可以判断两顶点是否已经联通 */
while (!pq.isEmpty()) {
int[] temp = pq.poll();
Node a = nodes[temp[1]].getSuper();
Node b = nodes[temp[2]].getSuper();
if (a != b) {
b.prev = a;
ret[temp[1]][temp[2]] = temp[0];
ret[temp[2]][temp[1]] = temp[0];
}
}
return ret;
}26.2.8 迪杰斯特拉算法
要计算一个连通图内，某一节点到图中另一节点的最短路径，可以采用 迪杰斯特拉算法（Dijkstra）
该算法是典型最短路径算法，采用广度优先搜索，以起始点为中心向外层层扩展，直到终点为止
#迪杰斯特拉算法步骤
-
设置出发点 v、顶点集合 V、距离集合 D。其中 v 为起始点，V 包含起始点外所有顶点，D[i] 表示 v 到 V[i] 的距离
-
找到 D[] 中的最小值 D[n] 和其对应的顶点 V[n]。此时D[n] 即为顶点 V[n] 到 v 的最小距离。
-
将 V[n] 设置为当前出发点，从 V 中移除 V[n]。
对 D 进行更新。D[i] 变成 (原本数值) 和 (当前顶点 v 与 V[i] 距离 + D[n]) 的较小一方数值
从 D 中移除 D[n]
-
重复 2 - 3，直到当前顶点变为终点。此时的行进距离即为最短路径
#迪杰斯特拉算法实现
public static int dijkstra(int[][] map, int start, int end) {
if (start == end) return 0;
/* 将顶点和边放入优先级队列，以便后续取出最短距离
对于其中任意元素 n 有：n[1] 为节点，n[0] 为 n[1] 与起始节点的最短距离 */
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(o->o[0]));
int n = map.length;
for (int i = 0; i < n; i++) {
if (i == start) continue;
int temp = map[start][i];
pq.add(new int[]{temp == 0 ? Integer.MAX_VALUE : temp, i});
}
/* 取出那个最短路径和对应节点，对剩余元素进行更新 */
while (!pq.isEmpty()) {
int[] temp = pq.poll();
if (temp[1] == end) return temp[0];
else if (temp[1] == Integer.MAX_VALUE) return -1;
for (int[] flush : pq) {
int dir = map[flush[1]][temp[1]];
if (dir != 0 && flush[0] > dir + temp[0]) flush[0] = dir + temp[0];
}
}
return -1;
}26.2.9 弗洛伊德算法
另一种最短路径算法是 弗洛伊德算法（Floyd）
I count weights!
迪杰斯特拉算法用于计算图中 某一顶点 到其他顶点的最短路径。
弗洛伊德算法用于计算图中 各个顶点 之间的最短路径。
#弗洛伊德算法步骤
-
对于任意顶点 a、b ，取任意中继节点 k，则 a、b 间最短路径 D(a,b) 是 [a、b 直接路径距离] 与 [D(a,k) + D(b,k)] 间的较小方数值
-
对于上面的 D(a,k) 和 D(b,k)，是以相同方式获得
-
要计算图中每个节点的最短路径，势必要用每个顶点（作为中继节点）对图进行更新。
用每个顶点进行更新时，对其他所有边进行更新。
#实现弗洛伊德算法
public static int[][] floyd(int[][] map) {
int n = map.length;
int[][] ret = new int[n][n];
for (int i = 0; i < n; i++) ret[i] = Arrays.copyOf(map[i], n);
/* 让每个节点做中继节点 */
for (int i = 0; i < n; i++) {
/* 取出节点 a */
for (int j = 1; j < n; j++) {
/* a 不能是中继节点，而且必须与中继节点相连
此处，由于 i == j 时 map[i][j] == 0，所以省略了 i == j 的判断 */
int part1;
if ((part1 = ret[i][j]) == 0) continue;
/* 取出节点 b */
for (int k = 0; k < j; k++) {
/* 对 b 的判断与对 a 的相同，即：不是中继节点，且与中继节点相连 */
int part2;
if ((part2 = ret[i][k]) == 0) continue;
int edge = ret[k][j]; // a、b 的直接路径距离
part2 += part1; // 通过中继节点的路径距离
/* 如有必要，进行更新 */
if (edge == 0 || edge > part2) {
ret[k][j] = part2;
ret[j][k] = part2;
}
}
}
}
return ret;
}26.2.10 埃氏筛、线性筛
要找出一定数字范围内，所有的质数，可以使用 埃氏筛 或 线性筛
#埃氏筛步骤
埃拉托斯特尼筛法，简称埃氏筛。虽然我们不能直接求出所有的质数，但可以求出所有的合数，这样余下的数就是质数。任何合数都能被分解为一个质数和另一个数的积，换言之，质数的倍数（除其本身）都是合数。
假设我们要求出小于 的所有质数。由于 的特殊性，我们将其直接排除。
接下来，我们依次枚举 范围内的数字 ，对其做如下操作
-
若该数被标记过（意味着 是某个质数的倍数），则其为合数。跳过该数
-
若该数未被标记（意味着 不是质数的倍数），则其为质数。可见第一个质数是
之后，标记该质数的所有小于 的倍数。
#实现埃氏筛
public static List<Integer> sieveEra(int n) {
List<Integer> prime = new LinkedList<>(); // 返回列表
boolean[] not_prime = new boolean[n+1]; // not_prime[i] 表示数字 i 是否是合数
/* 遍历检查 [2, n] 范围内的所有数 */
for (int i = 2; i <= n; i++) {
/* 首先进行判断，若为合数则跳过，为质数则添加到返回列表 */
if (not_prime[i]) continue;
prime.add(i);
/* 下面，将该质数的所有倍数标记为合数 */
for (int j = 2; j*i <= n; j++) not_prime[j*i] = true;
}
return prime;
}该算法的时间复杂度为
#线性筛步骤
埃氏筛在筛选过程中，每个合数必然会被不同质数重复标记。若能使每个合数都只被其最小质因数标记一次，就能减少标记次数，从而降低时间复杂度。
详见下面的代码。
#实现线性筛
public static List<Integer> sieveEul(int n) {
List<Integer> prime = new LinkedList<>(); // 返回列表
int[] mpf = new int[n+1]; // mpf[i] 表示数字 i 的最小质因数，质数有 mpf[i] = 0
/* 遍历检查 [2, n] 范围内的所有数 */
for (int i = 2; i <= n; i++) {
/* 若该数为质数则添加到返回列表 */
if (mpf[i] == 0) prime.add(i);
/* 从小到大顺序遍历先前找到的质数，与 i 相乘，其结果必然是合数 */
for (int p: prime) {
int t = i * p; // 下一个要标记的合数
if (t <= n) mpf[t] = p; // 若在范围内，则将其标记，否则跳出
else break;
/* mpf[i] 是数字 i 的最小质因数。
若当前遍历到的质数是数字 i 的最小质因数，则直接跳出。
下面证明该做法的合理性：
若遍历到的质数 p 是当前数字 i 的最小质因数，则 i 是 p 的正整数倍
设 i = k*p，则必有 k >= p，且 p 小于 k 的最小质因数（因为 p 是 i = k*p 的最小质因数）
若不在此处跳出：
对于 p 之后的任意质数 r，其与 i 的乘积为 r*i
有 r*i = r*(k*p) = (r*k)*p。
也就是说，合数 r*i 不仅会被 i 和 r 标记，也会被数字 r*k 和 p 再次标记。
若在此处跳出，则之后枚举到数字 r*k 时：
由于 r 是大于 p 的质数，而 p 小于 k 的最小质因数（因为 p 是 i = k*p 的最小质因数）
所以，合数 r*k 的最小质因数一定大于 p。换言之，r*k*p = r*i 会被标记。
综上所述：当前遍历到的质数 p 是数字 i 的最小质因数时，应该直接跳出 */
if (mpf[i] == p) break;
}
}
return prime;
}理论上该算法的时间复杂度为 ，但因为种种原因，有时候比埃氏筛要慢。
附录
骑士周游问题
将一枚骑士棋子放在国际象棋棋盘上。使骑士按照行棋规则移动，要求每个方格只能进入一次，最终走遍棋盘上所有方格。
穷举法效率较低，可以利用贪心算法进行优化。
每次行棋前，计算那些目标点位上包含的行棋方法的数量。行棋时，从最低数量的点位开始尝试。
@SuppressWarnings("ALL")
class Chess {
private int[][] chess = null; // 棋盘。chess[y][x] == 0 表示该格未被走过，否则是已被走过
private int[][] inner = null; // 数据棋盘。inner[y][x] 是 (x, y) 该格能通向几个未被走过的格子
private int goal = -1; // 本局游戏中，需要走过多少格子
private static final Comparator<int[]> c = Comparator.comparing(o->inner[o[1]][o[0]]);
// 比较器，期待传入的是数组形式的点位：int[] o
// 其中 o.length == 2，o[0] 为横坐标 x，o[1] 为纵坐标 y
// 该比较器比较该 o 点位的 inner 值，即 inner[o[1]][o[0]]
/* 进行一次马踏棋盘游戏 */
public void chess(int width, int height, int x, int y) {
/* 对初始的参数进行检查 */
if (width < 4 || width > 50 || height < 4 || height > 50 || x < 0 || x > width || y < 0 || y > height)
throw new RuntimeException("Illegal Chess Game");
/* 初始化参数 */
goal = width * height;
chess = new int[height][width];
inner = initialInner(width, height);
/* 进行游戏。成功时输出棋盘，否则提示失败 */
System.out.println(act(new int[]{x, y}, 1) ? deepToString(chess) : "失败");
}
/* 把棋子移动到该格。
该格的坐标是 (p[0], p[1])，这是棋子走的第 step 步 */
private boolean act(int[] p, int step) {
/* 把当前格子标记为已走过 */
chess[p[1]][p[0]] = step;
/* 如果走过了所有格子，则游戏结束 */
if (step >= goal) return true;
step++;
/* 查看有哪些能走的格子，将其放入一个优先级队列 */
int[][] aims = aims(p[0], p[1]);
Queue<int[]> q = new PriorityQueue<>(c); // 这个比较器是前面定义的，比较 inner 值的那个比较器
Stack<int[]> s = new Stack<>();
for (int[] i : aims) {
/* 点位合法时，让那个 inner 值减少（因为当前格子不能走了），并让其入列 */
if (check(i)) {
inner[i[1]][i[0]]--;
s.push(i);
q.add(i);
}
}
/* 从 inner 较小的点位开始，试着向目标格移动棋子 */
while (!q.isEmpty()) if (act(q.poll(), step)) return true;
/* 进行到这里说明没有有效走法，我们将该格子重新标记为未走过，并返回上一格 */
chess[p[1]][p[0]] = 0;
for (int[] i : s) inner[i[1]][i[0]]++;
return false;
}
/* 初始化那个数据棋盘。该方法仅在进入游戏时调用一次
这个方法不具有推广性。条件变化时（如棋盘变成六角形，或行棋规则变化），该方法应当重写 */
private static int[][] initialInner(int width, int height) {
int[][] inner = new int[height][width];
for (int i = 0; i < height; i++) {
int red = (i == 1 || i == height - 2) ? 2 : 0;
int div = (i == 0 || i == height - 1) ? 1 : 0;
for (int j = 0; j < width; j++) {
int r = (j == 1 || j == width - 2) ? red + 2 : red;
int d = (j == 0 || j == width - 1) ? div + 1 : div;
inner[i][j] = (8 - r) >> (d);
}
}
return inner;
}
/* 返回从 (x, y) 点位能到达的所有点位构成的数组，但不保证数组中每个点位都有效
这个方法也不具有推广性。条件变化时（如棋盘变成六角形，或行棋规则变化），该方法应当重写 */
private static int[][] aims(int x, int y) {
int[][] ret = new int[8][2];
boolean rx = false;
boolean ry = false;
for (int j = 0; j < 8; j++) {
ret[j][0] = x + (rx ? -1 : 1) * ((j + 4) / 4);
ret[j][1] = y + (ry ? -1 : 1) * ((11 - j) / 4);
if (ry = !ry) rx = !rx;
}
return ret;
}
/* 检查该点位是否有效 */
private boolean check(int[] i) {
if (i[0] < 0 || i[1] < 0 || i[1] >= inner.length || i[0] >= inner[i[1]].length) return false;
return chess[i[1]][i[0]] == 0;
}
/* 输出一个棋盘的信息 */
public static String deepToString(int[][] array) {
StringBuilder sb = new StringBuilder();
for (int[] ints : array) {
for (int i : ints) sb.append(i).append("\t");
sb.append("\n");
}
return sb.toString();
}
}