深度优先算法基础练习
1、POJ 2488
题意：给出一个国际棋盘的大小，判断马能否不重复的走过所有格，并记录下其中按字典序排列的第一种路径。
package knights_journey;
import java.util.Stack;
/**
* @Author jinjun99
* @Date Created in 2021/11/20 15:32
* @Description
* @Since version-1.0
*/
public class Demo {
private static int n = 6;
/**
* 棋盘
*/
private static int[][] cb = new int[n][n];
/**
* 方向
*/
private static int[][] dir = {{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
private static Stack<Integer[]> currPath = new Stack<>();
private static Stack<Integer[]> finalPath = new Stack<>();
private static int end = 0;
private static void dfs(int a,int b){
if (currPath.size()==n*n){
finalPath = (Stack<Integer[]>) currPath.clone();
end =1;
return ;
}
for (int i = 0; i < 8 && end ==0; i++) {
int q = a+dir[i][0];
int p = b+dir[i][1];
if (q<n && q>-1 && p<n && p>-1 && cb[q][p]==0){
cb[q][p] = 1;
currPath.push(new Integer[]{q,p});
dfs(q,p);
cb[q][p] = 0;
currPath.pop();
}
}
}
public static void main(String[] args) {
cb[2][1] = 1;
currPath.push(new Integer[]{2,1});
dfs(2,1);
int[][] path = new int[n][n];
path[2][1] = 1;
for (int i = n*n; i > 0; i--) {
Integer[] a = finalPath.pop();
int p = (int)a[0];
int q = (int)a[1];
path[p][q] = i;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (path[i][j]<10){
System.out.print(" "+path[i][j]+" ");
}else {
System.out.print(path[i][j]+" ");
}
if (j==n-1){
System.out.println();
}
}
}
}
}
/*输出：
2 5 16 13 36 25
7 12 3 26 17 14
4 1 6 15 24 35
11 8 31 20 27 18
32 21 10 29 34 23
9 30 33 22 19 28 */
2、POJ 3009
题意：要求把一个冰壶从起点“2”用最少的步数移动到终点“3”，其中0为移动区域，1为石头区域，冰壶一旦想着某个方向运动就不会停止，也不会改变方向（想想冰壶在冰上滑动），除非冰壶撞到石头1或者到达终点3，冰壶撞到石头后，冰壶会停在石头前面，此时（静止状态）才允许改变冰壶的运动方向，而该块石头会破裂，石头所在的区域由1变为0，也就是说，冰壶撞到石头后，并不会取代石头的位置。终点是一个摩擦力很大的区域，冰壶若到达终点3，就会停止在终点的位置不再移动。冰壶单次移动距离超过10或者碰到墙壁会失败。
package curling;
import java.util.Stack;
/**
* @Author jinjun99
* @Date Created in 2021/11/20 19:47
* @Description
* @Since version-1.0
*/
public class Deom01 {
private static int n = 8;
private static int[][] map = {
{2,0,0,1,0,0,0,0},
{0,0,0,1,0,1,0,0},
{0,1,1,1,0,1,0,0},
{0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,0,0},
{0,0,0,0,0,0,0,0},
{0,0,1,1,1,1,3,1},
{0,0,0,0,0,0,0,0},};
private static int[] dirX = {0,1,0,-1};
private static int[] dirY = {1,0,-1,0};
private static int currStep = 0;
private static int minStep = 0;
public static void main(String[] args) {
map[0][0] = 2;
map[6][7] = 3;
dfs(0,0);
System.out.println("最小步数为："+minStep);
}
private static void dfs(int x, int y){
for (int i = 0; i < 4; i++) {
int a = x;
int b = y;
for (int j = 0; j <10; j++) {
a+=dirX[i];
b+=dirY[i];
if (a<0||a>=n||b<0||b>=n){
break;
}
if (map[a][b]==3){
currStep+=(j+1);
if (currStep<minStep||minStep==0){
minStep = currStep;
}
currStep-=(j+1);
break;
}
if (map[a][b]==1){
currStep+=j;
map[a][b]=0;
dfs(a-dirX[i],b-dirY[i]);
currStep-=j;
map[a][b]=1;
break;
}
}
}
}
}
/*最小步数为：12*/
3、POJ 1088
Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
package skiing;
import java.util.Stack;
/**
* @Author jinjun99
* @Date Created in 2021/11/19 21:37
* @Description
* @Since version-1.0
*/
public class Demo02 {
private static int r = 5;
private static int c = 5;
private static int[][] heightMap = {
{1 , 2, 3, 4, 5},
{16,17,18,19, 6},
{15,24,25,20, 7},
{14,23,22,21, 8},
{13,12,11,10, 9}};
private static Stack<Integer> currPath = new Stack<>();
private static Stack<Integer> shortestPath = new Stack<>();
public static void main(String[] args) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
backTrack(i,j);
}
}
System.out.println("最大长度："+shortestPath.size());
System.out.println("最长路径：");
System.out.println(shortestPath);
}
private static void backTrack(int i,int j){
currPath.push(heightMap[i][j]);
int b=1;
if (i<r-1&&heightMap[i+1][j]<heightMap[i][j]){
backTrack(i+1,j);
b=0;
}
if (i>0&&heightMap[i-1][j]<heightMap[i][j]){
backTrack(i-1,j);
b=0;
}
if (j<c-1&&heightMap[i][j+1]<heightMap[i][j]){
backTrack(i,j+1);
b=0;
}
if (j>0&&heightMap[i][j-1]<heightMap[i][j]){
backTrack(i,j-1);
b=0;
}
if (b==1&&currPath.size()>shortestPath.size()){
shortestPath = (Stack<Integer>) currPath.clone();
}
currPath.pop();
}
}
/*
最大长度：25
最长路径：
[25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
*/
4、迷宫问题
用一个二维数组表示迷宫，1代表障碍，0代表可通过，然后问从头到尾一共有几条路径可以走到终点，这个问题同样是dfs加回溯，就是遍历每一个走过点的上下左右四个方向，直到最后走到终点再重新回溯就是return 1，把走过的还原为0,（因为走过的路都标记为1），最后return sum把顺带可以return的结果输出。
地图：
0 0 0 1 0 0 0 0
0 0 0 1 0 1 0 0
0 1 1 1 0 1 0 0
0 0 0 0 0 1 0 0
1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0
package maze;
/**
* @Author jinjun99
* @Date Created in 2021/11/20 10:38
* @Description 求迷宫从起点到终点共有多少条路径
* @Since version-1.0
*/
public class Demo02 {
//迷宫行列数
private static int n = 8;
//迷宫图
private static int[][] maze = {
{0,0,0,1,0,0,0,0},
{0,0,0,1,0,1,0,0},
{0,1,1,1,0,1,0,0},
{0,0,0,0,0,1,0,0},
{1,1,1,1,1,1,0,0},
{0,0,0,0,0,0,0,0},
{0,0,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0},};
//标记走过的位置
private static int[][] sign = new int[n][n];
private static int dfs(int x,int y){
//如果越界，撞墙或已走过，返回0
if (x==n||x<0||y==n||y<0||sign[x][y]==1||maze[x][y]==1){
return 0;
}
//如果走到终点，返回1
if (x==n-1&&y==n-1){
return 1;
}
//标记走过的点
sign[x][y]=1;
int count = 0;
count += dfs(x+1,y);
count += dfs(x-1,y);
count += dfs(x,y+1);
count += dfs(x,y-1);
//回溯
sign[x][y]=0;
return count;
}
public static void main(String[] args) {
int sum = dfs(0,0);
System.out.println("路径数："+sum);
}
}
/*路径数：384*/