算法题

 1 import org.junit.jupiter.api.Test;
 2 
 3 /**
 4  * @program: Algorithms
 5  * @ClassName Solution
 6  * @description: 找迷宫出口
 7  * @author: 一叶之秋
 8  * @create: 2021-05-17 11:00
 9  * @Version 1.0
10  **/
11 public class Solution {
12     public boolean maze(char[][] a) {
13         int row = a.length;
14         int col = a[0].length;
15 
16         //定位玩家起点位置
17         int location_x = 0;
18         int location_y = 0;
19         boolean flagFind = false;
20         for (location_x = 0; location_x < row; location_x++) {
21             for (location_y = 0; location_y < col; location_y++){
22                 if (a[location_x][location_y] == ‘%‘){
23                     flagFind = true;
24                     break;
25                 }
26             }
27             if (flagFind) break;;
28         }
29 
30         return findPath(a,location_x,location_y);
31     }
32 
33     public boolean findPath(char[][] a,int x,int y){
34         if (x == a.length - 1 || x == 0 || y == a[0].length - 1 || y == 0){
35             return true;
36         }else {
37             //按照下，右，上，左的策略递归
38             if (a[x+1][y] == ‘0‘){
39                 a[x+1][y] = ‘#‘;
40                 if (findPath(a,x+1,y))
41                     return true;
42                 else
43                     a[x+1][y] = ‘0‘;
44             }
45             if (a[x][y+1] == ‘0‘){
46                 a[x][y+1] = ‘#‘;
47                 if (findPath(a,x,y+1))
48                     return true;
49                 else
50                     a[x][y+1] = ‘0‘;
51             }
52             if (a[x-1][y] == ‘0‘){
53                 a[x-1][y] = ‘#‘;
54                 if (findPath(a,x-1,y))
55                     return true;
56                 else
57                     a[x-1][y] = ‘0‘;
58             }
59             if (a[x][y-1] == ‘0‘){
60                 a[x][y-1] = ‘#‘;
61                 if (findPath(a,x,y-1))
62                     return true;
63                 else
64                     a[x][y-1] = ‘0‘;
65             }
66                 return false;
67         }
68     }
69 
70     @Test
71     public void test(){
72         char[][] a = {
73                 {‘1‘,‘1‘,‘1‘,‘1‘,‘1‘,‘1‘,‘0‘,‘1‘,‘1‘,‘1‘},
74                 {‘1‘,‘0‘,‘1‘,‘1‘,‘1‘,‘1‘,‘0‘,‘1‘,‘0‘,‘1‘},
75                 {‘1‘,‘0‘,‘0‘,‘0‘,‘1‘,‘0‘,‘0‘,‘1‘,‘0‘,‘1‘},
76                 {‘1‘,‘0‘,‘1‘,‘0‘,‘1‘,‘0‘,‘1‘,‘0‘,‘0‘,‘1‘},
77                 {‘1‘,‘0‘,‘1‘,‘0‘,‘0‘,‘0‘,‘0‘,‘0‘,‘1‘,‘1‘},
78                 {‘1‘,‘0‘,‘1‘,‘1‘,‘0‘,‘1‘,‘0‘,‘1‘,‘1‘,‘1‘},
79                 {‘1‘,‘1‘,‘1‘,‘1‘,‘0‘,‘1‘,‘0‘,‘0‘,‘0‘,‘1‘},
80                 {‘1‘,‘1‘,‘0‘,‘1‘,‘0‘,‘1‘,‘0‘,‘1‘,‘0‘,‘1‘},
81                 {‘1‘,‘0‘,‘%‘,‘0‘,‘0‘,‘1‘,‘0‘,‘0‘,‘0‘,‘1‘},
82                 {‘1‘,‘1‘,‘1‘,‘1‘,‘1‘,‘1‘,‘1‘,‘1‘,‘1‘,‘1‘}
83         };
84         System.out.println(maze(a));
85         for (int i = 0; i < a.length; i++) {
86             for (int j = 0; j < a[0].length; j++) {
87                 System.out.print(a[i][j] + " ");
88             }
89             System.out.println();
90         }
91 
92     }
93 }

 1 import org.junit.jupiter.api.Test;
 2 
 3 /**
 4  * @program: Algorithms
 5  * @ClassName Solution2
 6  * @description: 连锁挖矿
 7  * @author: 一叶之秋
 8  * @create: 2021-05-17 11:45
 9  * @Version 1.0
10  **/
11 public class Solution2 {
12     public void destroy(int x,int y,char[][] blocks){
13         char aim = blocks[x][y];
14         blocks[x][y] = ‘#‘;
15         chainDestory(x,y,aim,blocks);
16     }
17     public void chainDestory(int x,int y,char aim,char[][] blocks){
18         if (x+1 < blocks.length && blocks[x+1][y] == aim){
19             blocks[x+1][y] = ‘#‘;
20             chainDestory(x+1,y,aim,blocks);
21         }
22         if (x-1 > 0 && blocks[x-1][y] == aim){
23             blocks[x-1][y] = ‘#‘;
24             chainDestory(x-1,y,aim,blocks);
25         }
26         if (y-1 > 0 && blocks[x][y-1] == aim){
27             blocks[x][y-1] = ‘#‘;
28             chainDestory(x,y-1,aim,blocks);
29         }
30         if (y+1 < blocks[0].length && blocks[x][y+1] == aim){
31             blocks[x][y+1] = ‘#‘;
32             chainDestory(x,y+1,aim,blocks);
33         }
34     }
35 
36 
37     @Test
38     public void test(){
39         int size = 8;
40         char[][] blocks = new char[size][size];
41         for (int i = 0; i < size; i++) {
42             for (int j = 0; j < size; j++) {
43                 blocks[i][j] = (char)(‘0‘ + Math.random() * 3);
44             }
45         }
46         for (int i = 0; i < size; i++) {
47             for (int j = 0; j < size; j++) {
48                 System.out.print(blocks[i][j] + " ");
49             }
50             System.out.println();
51         }
52         System.out.println("-----------------------------------");
53         int x = (int)(Math.random() * size);
54         int y = (int)(Math.random() * size);
55         System.out.print("x : " + x + "   ");
56         System.out.println("y : " + y + "   ");
57         System.out.println("-----------------------------------");
58         destroy(x,y,blocks);
59         for (int i = 0; i < size; i++) {
60             for (int j = 0; j < size; j++) {
61                 System.out.print(blocks[i][j] + " ");
62             }
63             System.out.println();
64         }
65     }
66 
67 
68 }