GDPU 竞赛技能实践 天码行空4 搜索plus

大家好，欢迎来到IT知识分享网。

一、目的：

1. 掌握递归和排序
2. 掌握BFS与队列
3. 掌握DFS和递归
4. 熟悉并理解回溯问题

二、实验内容：

1.八数码问题

在一个3×3的棋盘上，放置编号为1~8的8个方块，每个占一格，另外还有一个空格。与空格相邻的数字方块可以移动到空格里。

任务1：指定初始棋局和目标棋局，计算出最少的移动步数；

任务2：输出数码的移动序列。

输入案例
二维棋盘压缩成一维，输入的 x 表示空格
第一行输入初始棋盘，第二行输入目标前

23415x768 x 

输出案例

空格移动的步骤：上左左下下右上右下左左上右右下左上右下 空格移动的步数为：19 

💖 BFS

Cpp

#include <iostream> #include <cstring> #include <algorithm> #include <queue> #include <unordered_map> using namespace std; int dx[4] = { 
   -1, 0, 1, 0}, dy[4] = { 
   0, 1, 0, -1}; string li[4] = { 
   "上", "右", "下", "左"}; int bfs(string s,string end) { 
    queue <string> q; unordered_map<string, int> dist; unordered_map<string, string> list; dist[s] = 0; list[s] = ""; q.push(s); while (q.size()) { 
    string t = q.front(); q.pop(); int dis = dist[t]; string lis = list[t]; if (t == end) { 
    puts(lis.c_str()); return dis; } int k = t.find('x'); int x = k / 3, y = k % 3; for (int i = 0; i < 4; i ++ ) { 
    int a = x + dx[i], b = y + dy[i]; if (0 <= a && a < 3 && 0 <= b && b < 3) { 
    swap(t[k], t[a * 3 + b]); if (!dist.count(t)) { 
    dist[t] = dis + 1, q.push(t); list[t] = lis + li[i]; } swap(t[k], t[a * 3 + b]); } } } puts("无解！！"); return -1; } int main() { 
    string start,end; cin >> start >> end; // for (int i = 1; i <= 9; i ++ ) // { 
    // string s; // cin >> s; // strat += s; // } int steps = bfs(start,end); if(steps != -1) cout << "总步数为：" << steps; return 0; } 

Java

import java.util.*; public class 八数码 { 
    // 位移数组 static int[] dx = { 
    -1, 0, 1, 0 }; static int[] dy = { 
    0, 1, 0, -1 }; static String[] move = { 
    "上", "右", "下", "左" }; static String end;// 终点 public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); String start = sc.next(); end = sc.next(); int steps = bfs(start); if (steps != -1) System.out.println("空格移动的步数为：" + steps); } private static int bfs(String start) { 
    LinkedList<String> q = new LinkedList<>();// BFS当前层的队列 HashMap<String, Integer> dist = new HashMap<>();// 步骤数 HashMap<String, String> list = new HashMap<>();// 存移动的历史记录 dist.put(start, 0); list.put(start, ""); q.add(start); while (!q.isEmpty()) { 
    String t = q.poll(); int steps = dist.get(t);// 当前的步骤数 String path = list.get(t);// 移动的历史记录 if (end.equals(t))// 说明到达终点 { 
    System.out.println("空格移动的步骤：" + path); return steps; } int k = t.indexOf('x');// 找到当前的空格位置 int x = k / 3; int y = k % 3; for (int i = 0; i < 4; i++) { 
    int xx = x + dx[i];// 要移动到的横坐标 int yy = y + dy[i];// 要移动到的纵坐标 if (xx >= 0 && xx < 3 && yy >= 0 && yy < 3) { 
    String newStr = swap(t, k, xx * 3 + yy);// 移动 if (!dist.containsKey(newStr))// 去重 { 
    dist.put(newStr, steps + 1);// 步数 + 1 // q.push(newStr); //错误示例：将元素加入队首 q.add(newStr);// 将元素加入队尾 list.put(newStr, path + move[i]);// 记录操作步骤 } } } } System.out.println("无解！"); return -1; } / * 交换字符串 s 中 a，b下标的字符，并返回交换后的字符串 */ private static String swap(String s, int a, int b) { 
    char[] ss = s.toCharArray(); char t = ss[a]; ss[a] = ss[b]; ss[b] = t; return String.valueOf(ss); } } 

💖 双向BFS

import java.util.*; public class 八数码plus { 
    static class Pair { 
    int d;// 当前点到终点估计的距离 String sta;// 存当前的状态 public Pair(int d, String sta) { 
    super(); this.d = d; this.sta = sta; } } static class Pair2 { 
    String s; String c; public Pair2(String s, String c) { 
    super(); this.s = s; this.c = c; } } // 返回 状态m 中 1-8 中每个数 到 终点的 位置 的哈夫曼距离 之和 static int f(String m) { 
    int dt = 0; for (int i = 0; i < 9; i++)// 枚举当前状态的每个坑位对应的数 if (m.charAt(i) != 'x')// { 
    int t = m.charAt(i) - '1';// t 当前坑位上的数 // t 的 终点位置 (t/3,t%3), t 的当前位置(i/3,i%3),求哈夫曼距离 dt = dt + Math.abs(i / 3 - t / 3) + Math.abs(i % 3 - t % 3); } return dt; } // 交换 x 中 a,b两个位置上的字符 static String swap(String s, int a, int b) { 
    char[] cc = s.toCharArray(); cc[a] = s.charAt(b); cc[b] = s.charAt(a); String res = String.valueOf(cc); return res; } static String bfs(String start, String end) { 
    HashMap<String, Integer> d = new HashMap<>();// 存距离<状态,距离> // 小根堆实现 A星 BFS PriorityQueue<Pair> heap = new PriorityQueue<>((o1, o2) -> o1.d - o2.d); // 存路径（当前状态的上一状态 + 操作类型） HashMap<String, Pair2> pre = new HashMap<>(); // char[] op = { 'u', 'd', 'l', 'r' };// 四种交换操作 String[] op = { 
    "上", "下", "左", "右" };// 四种交换操作 // 四个方向，必须与四种交换操作一一对应 int[] dx = { 
    -1, 1, 0, 0 }; int[] dy = { 
    0, 0, -1, 1 }; heap.add(new Pair(f(start), start));// 起点进堆 d.put(start, 0);// 距离初始化为 0 while (!heap.isEmpty()) { 
    // 取出当前距离最近的点,出堆的点距离已经确定为最优解 Pair t = heap.poll(); String sta = t.sta;// 当前状态 if (sta.equals(end))// 终点出队就退出 break; int x = 0, y = 0;// 记录 x 的坐标 for (int i = 0; i < 9; i++) if (sta.charAt(i) == 'x') { 
    x = i / 3; y = i % 3; break; } // 宽搜四种交换方案 for (int i = 0; i < 4; i++) { 
    // xx,yy求新的 x 的坐标 int xx = x + dx[i]; int yy = y + dy[i]; if (xx < 0 || xx > 2 || yy < 0 || yy > 2)// 非法越界 continue; String newsta = swap(sta, xx * 3 + yy, x * 3 + y);// 交换后的状态 // 新状态以前没有搜到过 || 之前的距离大于当前状态 sta 交换到 newsta 的距离  if (!d.containsKey(newsta) || d.get(newsta) > d.get(sta) + 1) { 
    d.put(newsta, d.get(sta) + 1);// 更新当前距离 // 把 起点到 newsta的距离 + 预测newsta到终点的距离 和当前状态放入堆中 heap.add(new Pair(f(newsta) + d.get(newsta), newsta)); // 记录 newsta 的上一个 转移状态 和 对应的交换操作 pre.put(newsta, new Pair2(sta, op[i])); } } } String ans = ""; while (end != start) { 
    ans += pre.get(end).c; end = pre.get(end).s; } ans = new StringBuffer(ans).reverse().toString(); return ans; } public static void main(String[] args) { 
    Scanner sc = new Scanner(System.in); String start = sc.next(); String end = sc.next(); // String end = "x";// 表示终点 String step = bfs(start, end); System.out.println("需要移动的步数为：" + step.length() + "\n空格移动序列为：" + step); } } 

2.八皇后问题

在棋盘上放置8个皇后，使它们不同行、不同列、不同对角线。问有多少种合法的情况。

答：92种

💖 Java版

public class 八皇后 { 
    // 版本2(从左上到右下，按格子放皇后) static int N = 20; // 由于斜线的原因，至少开 2n-1 的空间 static int n; // n皇后问题 static char[][] g = new char[N][N]; // 存储皇后的信息 // 布尔类型默认值为 flase static boolean[] col = new boolean[N]; // 列 static boolean[] row = new boolean[N]; // 列 // 正对角线 u = -i + b --> b = u + i static boolean[] dg = new boolean[N]; // 反对角线 u = i + b --> b = u - i 但是 b 不能小于0，所以b = n - (u - i) = n - u + i static boolean[] udg = new boolean[N]; static int cnt = 0;// 记录方案数 / * @param x 行 * @param y 列 * @param s 皇后个数 */ static void dfs(int x, int y, int s) { 
    if (y == n) { 
   // 列标 溢出 y = 0; x++;// 转到下一行 } if (x == n) { 
    if (s == n) { 
    // 放满8个皇后 print(); } return; } // 不放皇后 dfs(x, y + 1, s); // 放皇后 if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) { 
    g[x][y] = 'Q'; row[x] = col[y] = dg[x + y] = udg[x - y + n] = true; dfs(x, y + 1, s + 1); row[x] = col[y] = dg[x + y] = udg[x - y + n] = false; g[x][y] = '.'; } } // 输出当前棋盘 private static void print() { 
    System.out.println("方案" + ++cnt); for (int i = 0; i < n; i++) { 
    for (int j = 0; j < n; j++) { 
    System.out.print(g[i][j]); } System.out.println(); } System.out.println(); } public static void main(String[] args) { 
    n = 8;// 八皇后 // 初始化棋盘 for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) g[i][j] = '.'; dfs(0, 0, 0); System.out.println("总方案数为：" + cnt); } } 

💖 C语言版

#include <stdio.h> // 包含标准输入输出库的头文件 #define N 20 // 定义一个常量N，代表棋盘大小 int n; // 定义一个全局变量n，表示棋盘的行数和列数 char g[N][N]; // 定义一个二维字符数组g，用于表示棋盘 int col[N], row[N], dg[N], udg[N]; // 定义四个数组，用于标记列、行和两个对角线是否已经放置了皇后 int cnt = 0; // 定义一个全局变量cnt，用于记录方案的数量 // 打印当前棋盘状态的函数 void print() { 
    printf("方案%d\n", ++cnt); // 打印方案编号 for (int i = 0; i < n; i++) { 
    // 遍历每一行 for (int j = 0; j < n; j++) { 
    // 遍历每一列 printf("%c", g[i][j]); // 打印当前格子的状态 } printf("\n"); // 每打印完一行后换行 } printf("\n"); // 每打印完一个方案后换行 } // 深度优先搜索函数，用于搜索所有可能的皇后放置方案 void dfs(int x, int y, int s) { 
    if (y == n) { 
    // 如果y坐标达到n，说明一行已经放置完毕 y = 0; // 重置y坐标，开始新的一行 x++; // 移动到下一行 } if (x == n) { 
    // 如果x坐标达到n，说明已经放置了n个皇后，找到一个方案 if (s == n) { 
    // 检查是否所有皇后都已放置 print(); // 如果是，打印当前方案 } return; // 结束递归 } dfs(x, y + 1, s); // 递归调用，尝试在当前行下一个位置放置皇后 // 检查当前位置是否可以放置皇后 if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) { 
    g[x][y] = 'Q'; // 放置皇后 row[x] = col[y] = dg[x + y] = udg[x - y + n] = 1; // 标记当前位置已放置皇后 dfs(x, y + 1, s + 1); // 递归调用，尝试放置下一行的皇后 row[x] = col[y] = dg[x + y] = udg[x - y + n] = 0; // 回溯，撤销当前位置的皇后 g[x][y] = '.'; // 恢复棋盘状态 } } int main() { 
    n = 8; // 设置棋盘大小为8 for (int i = 0; i < n; i++) // 初始化棋盘，所有格子状态为'.' for (int j = 0; j < n; j++) g[i][j] = '.'; dfs(0, 0, 0); // 从棋盘左上角开始深度优先搜索 printf("总方案数为：%d\n", cnt); // 打印所有可能的皇后放置方案总数 return 0; // 程序结束 }