- 要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）
一共有多少种可能的填数方案？
答案：
// 方格填数
public class Sy2 {
public static void main(String[] args) {
// TODO Auto-generated method stub
Block bk = new Block();
bk.init();
bk.addNum(0);// , 0, 0);
System.out.println("一共" Block.sum "种方案");
}
}
class Block {
public int[][] b = new int[3][4];
public static int sum;
/**
* 初始化整个数组
*/
public void init() {
for (int i = 0; i < 3; i ) {
for (int j = 0; j < 4; j ) {
b[i][j] = -2;
}
}
}
/**
* @param y y行
* @param x x列
* @param n 填数n
* @return 返回此方格是否能填数
*/
public boolean isAble(int y, int x, int n) {
// y行 x列 填数n
if (b[y][x] != -2)
return false;
for (int j = y - 1; j <= y 1; j ) {
for (int i = x - 1; i <= x 1; i ) {
if (j < 3 && j >= 0 && i < 4 && i >= 0) {
if (b[j][i] == n - 1 || b[j][i] == n 1) {
return false;
}
}
}
}
return true;
}
/**
* @param n 填入数字n
*/
public void addNum(int n) {
if (n > 9) {
sum ;
return;
}
for (int i = 0; i < 3; i ) {
for (int j = 0; j < 4; j ) {
if ((i == 0 && j == 0) || (i == 2 && j == 3))
continue;
// 如果此方格能填数，则填入数字
if (this.isAble(i, j, n)) {
b[i][j] = n;
this.addNum(n 1);// , y, x 1);
b[i][j] = -2; // 当加入下一个不行返回后，还原现在方块，继续循环
}
}
}
}
}
程序运行结果：
一共1580种方案
蛙跳河
在一个 5*5 的地图上，一只蛙欲从起点跳到目的地。中间有一条河（如图），但这只蛙不会游泳，并且每次跳只能横着跳一格或者竖着跳一格。（聪明的蛙不会跳已经跳过的路）
- 总共有多少种跳法。
- 给出路径最短的跳法。
答案：
- 明确函数功能：jump(m, n)为跳到(m, n)位置。
- 寻找递归出口：不在边界之内 或 已走过。
- 明确所有路径：右跳、左跳、下跳、上跳
- 回溯还原现场：
path--; // 回溯法关键步骤
a[m][n] = 0;
//青蛙跳
public class Sy1 {
static int count = 0; // 跳法种类计数
static int x = 4, y = 4; // 目的坐标
static int step = 0; // 记录步数
// 地图，0代表没有走过，1 代表已经走过
static int[][] map = { { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 }, { 1, 1, 0, 1, 1 }, { 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0 } };
static int min = 25; // 用来记录最小步数
static int sx[] = new int[25], sy[] = new int[25]; // 记录坐标
// 求解总共跳法，并求出最短步数，方便下面列出路径
static void jump(int m, int n) {
if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { // 该点在地图边界之内并且未走过
return;
}
map[m][n] = 1; // 走到此节点
step ;
if (m == x && n == y) { // 如果到达目的地
if (step < min)// 更新最短步数
min = step;
count ;
}
// 所有路径
jump(m 1, n); // 右跳
jump(m - 1, n); // 左跳
jump(m, n 1); // 下跳
jump(m, n - 1); // 上跳
step--; // 回溯法关键步骤
map[m][n] = 0;
}
// 列出最短步数的路径
static void find(int m, int n) {
if (m < 0 || m >= 5 || n < 0 || n >= 5 || map[m][n] != 0) { // 该点在地图边界之内并且未走过
return;
}
// 记录坐标
sx[step] = m;
sy[step] = n;
// 走到此节点
map[m][n] = 1;
step ;
if (m == x && n == y && step == min) { // 到达目的且为最短路径
int p = min - 1;
System.out.print("最短 path:" p "步");
for (int i = 0; i < min; i )
System.out.print("(" sx[i] "," sy[i] ")");
System.out.println();
}
find(m 1, n);
find(m - 1, n);
find(m, n 1);
find(m, n - 1);
step--;
map[m][n] = 0;
}
public static void main(String[] args) {
jump(0, 0);
step = 0;
System.out.println("总共" count "种解法");
find(0, 0);
}
}
程序运行结果：
走迷宫
以一个 M×N 的长方阵表示迷宫， 0 和 1 分别表示迷宫中的 通路 和 障碍 。
设计一个程序，对任意输入的迷宫，输出一条从入口到出口的通路，或得出没有通路的结论。
例：
输入：
请输入迷宫的行数 9
请输入迷宫的列数 8
请输入 9 行 8 列的迷宫
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
为了方便大家观看，我换成了矩阵：
001000100010001000101101011100100001000001000101011110011100010111000000001000100010001000101101011100100001000001000101011110011100010111000000
输出：
有路径
路径如下：
# # 1 0 0 0 1 0
0 # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
为了方便大家观看，我换成了矩阵：
##1000100#100010##101101#1110010###1###001###1#1011110#1110001#1110000####1000100#100010##101101#1110010###1###001###1#1011110#1110001#1110000##
答案：这里用栈来实现的递归，算是一个新思路。
//迷宫
/*位置类*/
class Position {
int row;
int col;
public Position() {
}
public Position(int row, int col) {
this.col = col;
this.row = row;
}
public String toString() {
return "(" row " ," col ")";
}
}
/*地图类*/
class Maze {
int maze[][];
private int row = 9;
private int col = 8;
Stack<Position> stack;
boolean p[][] = null;
public Maze() {
maze = new int[15][15];
stack = new Stack<Position>();
p = new boolean[15][15];
}
/*
* 构造迷宫
*/
public void init() {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入迷宫的行数");
row = scanner.nextInt();
System.out.println("请输入迷宫的列数");
col = scanner.nextInt();
System.out.println("请输入" row "行" col "列的迷宫");
int temp = 0;
for(int i = 0; i < row; i) {
for(int j = 0; j < col; j) {
temp = scanner.nextInt();
maze[i][j] = temp;
p[i][j] = false;
}
}
}
/*
* 回溯迷宫，查看是否有出路
*/
public void findPath() {
// 给原始迷宫的周围加一圈围墙
int temp[][] = new int[row 2][col 2];
for(int i = 0; i < row 2; i) {
for(int j = 0; j < col 2; j) {
temp[0][j] = 1;
temp[row 1][j] = 1;
temp[i][0] = temp[i][col 1] = 1;
}
}
// 将原始迷宫复制到新的迷宫中
for(int i = 0; i < row; i) {
for(int j = 0; j < col; j) {
temp[i 1][j 1] = maze[i][j];
}
}
// 从左上角开始按照顺时针开始查询
int i = 1;
int j = 1;
p[i][j] = true;
stack.push(new Position(i, j));
while (!stack.empty() && (!(i == (row) && (j == col)))) {
if ((temp[i][j 1] == 0) && (p[i][j 1] == false)) {
p[i][j 1] = true;
stack.push(new Position(i, j 1));
j ;
} else if ((temp[i 1][j] == 0) && (p[i 1][j] == false)) {
p[i 1][j] = true;
stack.push(new Position(i 1, j));
i ;
} else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) {
p[i][j - 1] = true;
stack.push(new Position(i, j - 1));
j--;
} else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) {
p[i - 1][j] = true;
stack.push(new Position(i - 1, j));
i--;
} else {
stack.pop();
if(stack.empty()) {
break;
}
i = stack.peek().row;
j = stack.peek().col;
}
}
Stack<Position> newPos = new Stack<Position>();
if (stack.empty()) {
System.out.println("没有路径");
} else {
System.out.println("有路径");
System.out.println("路径如下：");
while (!stack.empty()) {
Position pos = new Position();
pos = stack.pop();
newPos.push(pos);
}
}
/*
* 图形化输出路径
* */
String resault[][]=new String[row 1][col 1];
for(int k=0; k<row; k) {
for(int t=0; t<col; t) {
resault[k][t]=(maze[k][t]) "";
}
}
while (!newPos.empty()) {
Position p1=newPos.pop();
resault[p1.row-1][p1.col-1]="#";
}
for(int k=0; k<row; k) {
for(int t=0; t<col; t) {
System.out.print(resault[k][t] "\t");
}
System.out.println();
}
}
}
/*主类*/
class Sy4 {
public static void main(String[] args) {
Maze demo = new Maze();
demo.init();
demo.findPath();
}
}
程序运行结果：
嘿嘿，上面的那种用栈来实现递归的方法是不是看完了呢！把它放在第一个就是为了让大家以为没有递归回溯的答案，好认认真真的看完。。。（别打我）
贴心的我当然准备了用 递归回溯 方法的代码：
// 迷宫
class Sy4 {
public static void main(String[] args) {
Demo demo = new Demo();
demo.init();
demo.find(0, 0);
}
}
class Demo {
int m, n;
// 类在实例化时分配空间，但是只是逻辑上连续的空间，而不一定是物理上，毕竟有静态变量，不可能完全连续。
String[][] maze; //不能用char，扫描器Scanner不能扫描。
//这里只是声明，后面输入m、n时才能确定分配空间的大小
//初始化迷宫
public void init() {
Scanner scanner = new Scanner(System.in);
System.out.println("请输入迷宫的行数");
m = scanner.nextInt();
System.out.println("请输入迷宫的列数");
n = scanner.nextInt();
maze = new String[m][n];
System.out.println("请输入" m "行" n "列的迷宫");
for (int i = 0; i < m; i) {
for (int j = 0; j < n; j) {
maze[i][j] = scanner.next();
}
}
System.out.println("--------------------------------------------------------");
System.out.println("迷宫如下：");
for (int i = 0; i < m; i) {
for (int j = 0; j < n; j) {
System.out.print(maze[i][j] " ");
}
System.out.println();
}
System.out.println("--------------------------------------------------------");
}
//走到(x, y)点，找找路径
public void find(int x, int y) {
if (x < 0 || y < 0 || x >= m || y >= n || !maze[x][y].equals("0")) { // 注意字符串要用equals
return;
}
maze[x][y] = "#"; // 走到此节点
if (x == m - 1 && y == n - 1) {
for (int i = 0; i < m; i) {
for (int j = 0; j < n; j) {
System.out.print(maze[i][j] " ");
}
System.out.println();
}
System.out.println("--------------------------------------------------------");
}
find(x 1, y); //下移
find(x - 1, y); //上移
find(x, y 1); //右移
find(x, y - 1); //左移
maze[x][y] = "0";
}
}
程序运行结果：
--------------------------------------------------------
迷宫如下：
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
--------------------------------------------------------
# 0 1 0 0 0 1 0
# 0 1 0 0 0 1 0
# 0 1 0 1 1 0 1
# 1 1 1 # # 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# 0 1 0 0 0 1 0
# 0 1 0 0 0 1 0
# 0 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# 0 1 0 0 0 1 0
# # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 # # 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# 0 1 0 0 0 1 0
# # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# # 1 0 0 0 1 0
0 # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 # # 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# # 1 0 0 0 1 0
0 # 1 0 0 0 1 0
# # 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# # 1 0 0 0 1 0
# # 1 0 0 0 1 0
# 0 1 0 1 1 0 1
# 1 1 1 # # 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
# # 1 0 0 0 1 0
# # 1 0 0 0 1 0
# 0 1 0 1 1 0 1
# 1 1 1 0 0 1 0
# # # 1 # # # 0
0 1 # # # 1 # 1
0 1 1 1 1 0 # 1
1 1 0 0 0 1 # 1
1 1 0 0 0 0 # #
--------------------------------------------------------
马走日
假设国际象棋棋盘有 5*5 共 25 个格子。
设计一个程序，使棋子从初始位置（棋盘编号为 1 的位）开始跳马，能够把棋盘的格子全部都走一遍，每个格子只允许走一次。
- 输出一个如图 2 的解，左上角为第一步起点。
- 总共有多少解。
PS：国际象棋的棋子是在格子中间的。国际象棋中的“马走日”，如下图所示，第一步为[1,1],
第二步为[2,8]或[2,12]，第三步可以是[3,5]或[3,21]等，以此类推。
