/*
个人觉得这个题目给的提示太少，在短时间内很难看懂所有代码的思路， 但是仅仅看局部代码的话，填空题，，，，还是可以猜一猜的，，，*//*
题目：迷宫问题 内容： 迷宫问题对于走迷宫，人们提出过很多计算机上的解法。深度优先搜索、广度优先搜索是使用最广的方法。
生活中，人们更愿意使用“紧贴墙壁，靠右行走”的简单规则。 下面的代码则采用了另一种不同的解法。它把走迷宫的过程比做“染色过程”。 假设入口点被染为红色，它的颜色会“传染”给与它相邻的可走的单元。这个过程不断进行下去， 如果最终出口点被染色，则迷宫有解。仔细分析代码中的逻辑，填充缺少的部分。
把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。
public class Maze
{ class Cell { private int row; private int col; private Cell from; public Cell(int row, int col, Cell from) { this.row = row; this.col = col; this.from = from; } } char[][] maze = { {'#','#','#','#','B','#','#','#','#','#','#','#'}, {'#','#','#','#','.','.','.','.','#','#','#','#'}, {'#','#','#','#','.','#','#','#','#','.','.','#'}, {'#','.','.','.','.','#','#','#','#','#','.','#'}, {'#','.','#','#','#','#','#','.','#','#','.','#'}, {'#','.','#','#','#','#','#','.','#','#','.','#'}, {'#','.','#','#','.','.','.','.','.','.','.','#'}, {'#','.','#','#','.','#','#','#','.','#','.','#'}, {'#','.','.','.','.','#','#','#','.','#','.','#'}, {'#','#','.','#','.','#','#','#','.','#','.','A'}, {'#','#','.','#','#','#','.','.','.','#','#','#'}, {'#','#','#','#','#','#','#','#','#','#','#','#'}}; public void show() { for(int i=0; i<maze.length; i++) { for(int j=0; j<maze[i].length; j++) System.out.print(" " + maze[i][j]); System.out.println(); } } //把与from集合中相邻的可染色节点染色，被染色节点记入 dest //一旦发现出口将被染色，则返回当前的“传播源”节点 public Cell colorCell(Set<Cell> from, Set<Cell> dest) { Iterator<Cell> it = from.iterator(); while(it.hasNext()) { Cell a = it.next(); Cell[] c = new Cell[4]; c[0] = new Cell(a.row-1, a.col, a); c[1] = new Cell(a.row, a.col-1, a); c[2] = new Cell(a.row+1, a.col, a); c[3] = ___________________________; for(int i=0; i<4; i++) { if(c[i].row < 0 || c[i].row >= maze.length) continue; if(c[i].col < 0 || c[i].col >= maze[0].length) continue; char x = maze[c[i].row][c[i].col]; if(x=='B') return a; if(x=='.') { maze[c[i].row][c[i].col] = '?'; ____________________; } } } return null; } public void resolve() { Set<Cell> set = new HashSet<Cell>(); set.add(new Cell(9,11,null)); for(;;) { Set<Cell> set1 = new HashSet<Cell>(); Cell a = colorCell(set, set1); if(a!=null) { System.out.println("找到解！"); while(a!=null) { maze[a.row][a.col] = '+'; ______________; } break; } if(set1.isEmpty()) { System.out.println("无解！"); break; } set = set1; } } public static void main(String[] args) { Maze m = new Maze(); m.show(); m.resolve(); m.show(); } }*/1 import java.util.HashSet; 2 import java.util.Iterator; 3 import java.util.Set; 4 5 public class Maze{ //定义一个类，名叫 Maze， 6 7 class Cell{ //这是一个内部类， 8 private int row;//行， 9 private int col;//列， 10 private Cell from;//前驱， 11 12 public Cell(int row, int col, Cell from){ //构造方法， 13 this.row = row; 14 this.col = col; 15 this.from = from; 16 } 17 }//类的定义结束， 18 19 char[][] maze = { //这里存的是迷宫，名叫 maze，注意下面的代码都在这个类中，所以，他们都可以访问这个变量， 20 {'#','#','#','#','B','#','#','#','#','#','#','#'}, 21 {'#','#','#','#','.','.','.','.','#','#','#','#'}, 22 {'#','#','#','#','.','#','#','#','#','.','.','#'}, 23 {'#','.','.','.','.','#','#','#','#','#','.','#'}, 24 {'#','.','#','#','#','#','#','.','#','#','.','#'}, 25 {'#','.','#','#','#','#','#','.','#','#','.','#'}, 26 {'#','.','#','#','.','.','.','.','.','.','.','#'}, 27 {'#','.','#','#','.','#','#','#','.','#','.','#'}, 28 {'#','.','.','.','.','#','#','#','.','#','.','#'}, 29 {'#','#','.','#','.','#','#','#','.','#','.','A'}, 30 {'#','#','.','#','#','#','.','.','.','#','#','#'}, 31 {'#','#','#','#','#','#','#','#','#','#','#','#'} 32 }; 33 34 public void show() { //这个方法的作用是打印出这个迷宫， 35 for(int i=0; i from, Set dest) { //此方法的作用是染色，具体怎么染呢？先看下面resolve方法， 46 //set1没有初值，而set有初值，from没有初值，而dest有初值， 47 //我不知道为什么，但是这里dest貌似没有用到， 48 //这里from中只有一个元素， 49 Iterator it = from.iterator(); 50 while(it.hasNext())//这里it中只有一个元素 51 { 52 Cell a = it.next();//a = Cell(9,11,null) 53 Cell[] c = new Cell[4]; 54 //一下四句的意思是，a的四个方向的前驱都是自己， 55 c[0] = new Cell(a.row-1, a.col, a); 56 c[1] = new Cell(a.row, a.col-1, a); 57 c[2] = new Cell(a.row+1, a.col, a); 58 c[3] = new Cell(a.row, a.col+1, a);//这个填空明显送分， 59 60 for(int i=0; i<4; i++) 61 { 62 if(c[i].row < 0 || c[i].row >= maze.length) continue;//行超出， 63 if(c[i].col < 0 || c[i].col >= maze[0].length) continue;//列超出， 64 65 char x = maze[c[i].row][c[i].col];//得到a的四个方向的字符,‘B’‘#’‘A’‘.’ 66 if(x=='B') return a;//返回值在这里，//入口，这里返回了，，，， 67 if(x=='.') //a的某个方向有路， 68 { 69 maze[c[i].row][c[i].col] = '?';//这里是要把所有的路变成‘?’吗？ 70 dest.add(c[i]);//所以我猜这里和dest有关，//把所有的路装进dest,也就是set1, 71 } 72 } 73 } 74 return null;//返回值在这里， 75 } 76 77 public void resolve(){ //在这里， 78 Set set = new HashSet ();//定义一个HachSet变量set，此类实现 Set 接口， 79 //HachSet由哈希表（实际上是一个 HashMap 实例）支持。它不保证集合的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用 null 元素。 80 set.add(new Cell(9,11,null));//Set是一个没有重复元素的接口 81 82 for(;;) 83 { 84 Set set1 = new HashSet | ();//又定义了一个HachSet变量，set1，set1没有初值，而set有初值， 85 //这里是一个死循环，所以colorCell会调用很多次， 86 Cell a = colorCell(set, set1);//a为一个Cell内部类，这里调用了上面的染色方法，所以往上看 87 if(a!=null) 88 { 89 System.out.println("找到解！"); 90 while(a!=null) 91 { 92 maze[a.row][a.col] = '+'; 93 a = a.from; 94 } 95 break; 96 } 97 if(set1.isEmpty()) 98 { 99 System.out.println("无解！");100 break;101 }102 //现在有些明白了，colorCell中会改变set1的值，而这里set=set1，继续循环，103 set = set1;//没看明白这里为什么要循环，104 } 105 }106 107 public static void main(String[] args){ //main方法，108 Maze m = new Maze();//构造一个地图类，109 m.show();//打印初始地图110 m.resolve();//地图染色，111 m.show();//打印染色后地图112 }113 } | | | | | |
/*
难，抄的答案， Iterator<E> iterator() 返回在此 set 中的元素上进行迭代的迭代器。 boolean add(E o) 如果此集合中还不包含指定元素，则添加指定元素。 HashSet() 构造一个新的空集合，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75。 boolean hasNext() 如果仍有元素可以迭代，则返回 true。（换句话说，如果 next 返回了元素而不是抛出异常，则返回 true）。 E next() 返回迭代的下一个元素。重复调用此方法直到 hasNext() 方法返回 false，这将精确地一次性返回迭代器指向的集合中的所有元素。*/