深搜广搜算法

深搜

全排列

现有n个字符,要求进行全排列,比如abc三个字符,则有abcacbbacbcacabcba,6种排列。

java代码

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
public class Main{
private static char[] arr;//待全排列字符数组
private static char[] box;//盒子
private static boolean[] flag;//标记
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
arr = new char[n];
box = new char[n];
flag = new boolean[n];
for(int i = 0; i < n; i++){
arr[i] = in.next().charAt(0);
}
dfs(0); //核心算法
}
private static void dfs(int step){//前step个字符已排列,正在排列第step个字符
if(step == box.length) {//当全部字符排列完毕,输出并return
printf(box);
return;
}
for(int i = 0; i < box.length; i++){
if(flag[i]==true) continue;//第i个字符已使用则跳出
box[step] = arr[i];//将第i个字符放入第step个盒子
flag[i] = true;//标记第i个字符已使用
dfs(step+1);
flag[i] = false;//标记第i个字符未使用
}
}
private static void printf(char[] flag){
for(int i = 0; i < flag.length; i++){
System.out.print(flag[i]+" ");
}
System.out.println("");
}
}

走迷宫

现有一个n*m的迷宫,标记从起点(startx,starty)到终点(endx,endy)的一条路径
例如,0为可行,1为墙壁,2为走过的路径标记,起点为(0,0),终点为(3,3)

1
2
3
4
0 1 0 1
0 0 0 1
0 0 0 0
1 0 0 0
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
public class Main{

public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int startx = in.nextInt();
int starty = in.nextInt();
int endx = in.nextInt();
int endy = in.nextInt();
int[][] maze = new int[n+1][m+1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
maze[i][j] = in.nextInt();
}
}
maze[startx][starty] = 2;
dfs(startx,starty,endx,endy,maze);
}

private static void dfs(int startx, int starty, int endx, int endy, int[][] maze) {
if(startx==endx&&starty==endy){
printf(maze);
return;
}

if(startx-1 >= 1 && maze[startx-1][starty]==0){//往上走
maze[startx-1][starty]=2;
dfs(startx-1,starty,endx,endy,maze);
maze[startx-1][starty] = 0;
}

if(startx+1 <= maze.length-1 && maze[startx+1][starty]==0){//往下走
maze[startx+1][starty]=2;
dfs(startx+1,starty,endx,endy,maze);
maze[startx+1][starty]=0;
}

if(starty-1 >= 1 && maze[startx][starty-1]==0){//往左走
maze[startx][starty-1]=2;
dfs(startx,starty-1,endx,endy,maze);
maze[startx][starty-1]=0;
}

if(starty+1 <= maze[startx].length-1 && maze[startx][starty+1]==0){//往右走
maze[startx][starty+1]=2;
dfs(startx,starty+1,endx,endy,maze);
maze[startx][starty+1]=0;
}
}

private static void printf(int[][] arr){
for(int i = 0; i < arr.length; i++){
for(int j = 0; j < arr[i].length; j++){
System.out.print(arr[i][j]+" ");
}
System.out.println("");
}
}
}

广搜

走迷宫之最短路径

现有一个n*m的迷宫,输出从起点(startx,starty)到终点(endx,endy)的最短路径步数
例如,0为可行,*为墙壁,起点为(0,0),终点为(3,3)

1
2
3
4
0 1 0 1
0 0 0 1
0 0 0 0
1 0 0 0
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
public class Main{
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int startX = in.nextInt();
int startY = in.nextInt();
int endX = in.nextInt();
int endY = in.nextInt();
char[][] maze = new char[n+1][m+1];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
maze[i][j] = in.next().charAt(0);
}
}

int[] queueX = new int[n*n];//x坐标队列
int[] queueY = new int[n*n];//y坐标队列
int head = 0;//头指针
int tail = 1;//尾指针
queueX[head] = startX;//起点入队
queueY[head] = startY;
maze[queueX[head]][queueY[head]] = (char)('a');

while(tail-head>0){//判断队列不为空
int x = queueX[head];
int y = queueY[head];
printf(maze);
if(x==endX && y==endY){//到达终点
System.out.println(maze[endX][endY]-'a');
break;
}
if(x-1>=1 && maze[x-1][y]=='0'){//往左走
maze[x-1][y] = (char) (maze[x][y]+1);
queueX[tail] = x-1;//入队
queueY[tail] = y;
tail++;
}
if(x+1<=maze.length-1 && maze[x+1][y]=='0'){//往右走
maze[x+1][y] = (char) (maze[x][y]+1);
queueX[tail] = x+1;//入队
queueY[tail] = y;
tail++;
}
if(y-1>=1 && maze[x][y-1]=='0'){//往上走
maze[x][y-1] = (char) (maze[x][y]+1);
queueX[tail] = x;//入队
queueY[tail] = y-1;
tail++;
}

if(y+1<=maze[x].length-1 && maze[x][y+1]=='0'){//往下走
System.out.println((y+1)+","+maze[x].length+","+maze[x][y+1]);
maze[x][y+1] = (char) (maze[x][y]+1);
queueX[tail] = x;//入队
queueY[tail] = y+1;
tail++;
}
head++;//出队
}

}

private static void printf(char[][] maze){
for(int i = 1; i < maze.length; i++){
for(int j = 1; j < maze[i].length; j++){
System.out.print(maze[i][j]+" ");
}
System.out.println("");
}
System.out.println("");
}
}