实战
1.迷宫
package com.miao.recursion;
/**
* @author 缪广亮
* @version 1.0
*/
public class MazeDemo {
public static void main(String[] args) {
// 创建一个8行7列的二维数组
int[][] map = new int[8][7];
// 将第一行和最后一行赋值为1即0，7
for (int i = 0; i <8 ; i++) {
for (int j = 0; j <7 ; j++) {
map[0][j]=1;
map[7][j]=1;
}
}
// 将第一列和最后一列赋值为1即0和6
for (int i = 0; i <8 ; i++) {
for (int j = 0; j <7 ; j++) {
map[i][0]=1;
map[i][6]=1;
}
}
// 将第四行的二三列赋值为1即3,1和3，2
map[3][1]=1;
map[3][2]=1;
// 回溯
// map[1][2]=1;
// map[2][2]=1;
for (int[] row : map) {
for (int col : row) {
System.out.print(col+" ");
}
System.out.println();
}
Maze.findWay(map,1,1);
System.out.println("\nmap：");
for (int[] row : map) {
for (int col : row) {
System.out.print(col+" ");
}
System.out.println();
}
}
}
class Maze{
/**
*
* @param map 地图
* @param i 位置
* @param j
* @return 找到通路为true
* 使用递归回溯的方法
* 起始的位置是（1，1），若map[6][5]=2 表示已经找到路了
* map二维数组各值的含义
* 0：表示该点还未走过；1：表示为障碍物；2：表示该点为通路可以走；3：表示该点已经走过，为死路
* 找路的策略(多种)：下右上左，走不通则回溯
*/
public static boolean findWay(int[][] map,int i,int j){
if (map[6][5]==2)//表示已经找到了
return true;
else {
if (map[i][j]==0) {//该点还未走过
// 假设是通路可以走
map[i][j]=2;
// 使用策略下右上左
if (findWay(map,i+1,j))//下
return true;
else if (findWay(map,i,j+1))//右
return true;
else if (findWay(map,i-1,j))//上
return true;
else if (findWay(map,i,j-1))//左
return true;
else {
// 该点下右上左都走过，为死路
map[i][j]=3;
return false;
}
}else {
// 如果map[i][j]!=0,可能是1为障碍物，2，3为死路
return false;
}
}
}
}
2.八皇后
package com.miao.recursion;
/**
* @author 缪广亮
* @version 1.0
*/
public class Queue8 {
int max = 8;
static int count = 0;//用于记录皇后解法数
// 存放皇后位置的结果
int[] array = new int[max];
public static void main(String[] args) {
Queue8 queue8 = new Queue8();
queue8.check(0);
System.out.printf("一共有%d解法：", count);
}
// 放置第n个皇后
public void check(int n) {
if (n == max ) {//n=8,即8个皇后已放置好了
print();
return;
}
// 依次放入皇后，并判断是否冲突
for (int i = 0; i < max; i++) {
// 先把当前这个皇后n，放到该行的第一列
array[n] = i;
// 判断当前放置第n个皇后到i列时，是否冲突
if (judge(n)) //不冲突
// 接着放n+1个皇后，即开始递归
check(n + 1);
// 如果冲突，就继续执行array[n]=i;即将第n个皇后，放置在本行的后一列
}
}
// 查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
/**
* @param n 表示第n个皇后，n就代表行，且每次都在递增
* @return
* 下标i表示第i个皇后，而array[i]的值表示该皇后在的列
*/
public boolean judge(int n) {
for (int i = 0; i < n; i++) {
/*
array[i]==array[n] 表示判断第n个皇后是否和前面的n-1个皇后再同一列
Math.abs(n-i)==Math.abs(array[n]-array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线上
判断同一行，没有必要，n每次都在递增
*/
if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
return false;
}
}
return true;
}
// 打印已经在地图摆好的一组皇后
public void print() {
count++;//用于记录皇后解法数
for (int data : array) {
System.out.print(data + " ");
}
System.out.println();
}
}