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 }
单元测试结果