丶渲目 丶渲目
快到我碗里来
关注数: 14 粉丝数: 44 发帖数: 838 关注贴吧数: 24
程序填空---迷宫问题的困扰 import java.util.HashSet;import java.util.Iterator;import java.util.Set; /**@author *@version 创建时间:2013-4-26 上午10:55:15 */ public class Ti6 { /** * 6.代码填空 (满分19分)迷宫问题对于走迷宫,人们提出过很多计算机上的解法。深度优先搜索、广度优先搜索是使用最广的方法。生活中,人们更愿意使用“紧贴墙壁,靠右行走”的简单规则。下面的代码则采用了另一种不同的解法。它把走迷宫的过程比做“染色过程”。假设入口点被染为红色,它的颜色会“传染”给与它相邻的可走的单元。这个过程不断进行下去,如果最终出口点被染色,则迷宫有解。仔细分析代码中的逻辑,填充缺少的部分 把填空的答案(仅填空处的答案,不包括题面)存入考生文件夹下对应题号文件夹中的“解答.txt”中即可。 */ 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){S ystem.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){ Ti6 m = new Ti6(); m.show(); m.resolve(); m.show(); }}
1 下一页