1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
| import java.util.Scanner;
public class migong {
static int[][] map=new int[7][7];
static int[][] visited=new int[7][7];
static boolean flag=false;
static int nowlen;
static int minlen;
static String nowPath;
static String minPath;
static String nowPoint;
//四个方向，放在一个数组里
static int[][] fx=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++) {
if(i==0||j==0||i==6||j==6)//加一道墙
map[i][j]=1;
else{
map[i][j]=sc.nextInt();
}
}
}
minlen=Integer.MAX_VALUE;
nowlen=0;
visited[1][1]=0;
nowPath="";
minPath="";
dfs(1,1);
System.out.println(minlen);//输出最短
System.out.println(minPath);//输出最短路径
if(flag)
System.out.println("OK!");
else
System.out.println("NO!");
}
private static void dfs(int i, int j) {
//到达终点
if(i==5&&j==5){
flag=true;
if (nowlen<minlen) {//比较当前路径和最短路径的长度
minlen=nowlen;//保存最短路径的长度
minPath=new String(nowPath);//保存最短路径
}
visited[i][j]=0;//将终点重新标为没有访问的
System.out.println("Arrived!");
return;
}
for (int k = 0; k < 4; k++) {
if(check(i+fx[k][0],j+fx[k][1])){
visited[i+fx[k][0]][j+fx[k][1]]=1;//标记已经访问过的点
//试探
nowlen++;
nowPoint="(" + (i-1) + "," + (j-1) + ")"; // 输出当前访问的点
nowPath+=nowPoint;
System.out.println(nowPoint+" "+nowlen+" "+nowPath);
dfs(i+fx[k][0],j+fx[k][1]);
//回溯
nowlen--;
nowPath=nowPath.substring(0,nowPath.length()-nowPoint.length());
}
}
// //向下走
// if(check(i,j+1)){
// visited[i][j+1]=1;
// dfs(i,j+1);
// }
// //向右走
// if(check(i+1,j)){
// visited[i+1][j]=1;
// dfs(i+1,j);
// }
// //向上走
// if(check(i,j-1)){
// visited[i][j-1]=1;
// dfs(i,j-1);
// }
// //向左走
// if(check(i-1,j)){
// visited[i-1][j]=1;
// dfs(i-1,j);
// }
}
//检查是否可以走
private static boolean check(int i, int j) {
if(map[i][j]!=1&&visited[i][j]!=1)
return true;
else{
return false;
}
}
}
|
