从前有个迷宫__面试题
所有的代码不包括测试.
package com.mao.user;import java.awt.Point;import java.util.ArrayList;import java.util.List;public class 迷路小女孩 {private Point 位置 = new Point();private 指南针 方向 = 指南针.东; //初方向public Point get位置() {return 位置;}public void set位置(Point 位置) {this.位置 = 位置;}public 指南针 get方向() {return 方向;}public void set方向(指南针 方向) {this.方向 = 方向;}/** * 核心算法 * 1.作标记 * 2.找到所有的路 * 3.如果没有路就返回真 * 4.如果初始方向不能前进就改变方向 * 5.向着指定方向走一格 * @param maze * @return */public boolean 走一步(迷宫 maze){maze.撒面包(位置);List<指南针> ways = findWayOut(maze);if(ways.isEmpty()){return true;}else if(!ways.contains(方向)){方向 = ways.iterator().next();}else{// no change}方向.走(位置);return false;}/** * 老鼠向四个方向跑可以得到所有可以走的路 * @param maze * @return */public List<指南针> findWayOut(迷宫 maze){List<指南针> ways = new ArrayList<指南针>();for(指南针 way:指南针.values()){Point rate = new Point(位置);way.走(rate);if(!maze.掉下悬崖(rate)&&!maze.巨石压死(rate)){ways.add(way);}}return ways;}public static void main(String[] args) {迷宫 maze = new 迷宫(3);迷路小女孩 gril = new 迷路小女孩();gril.set位置(new Point(0,0));while (!gril.走一步(maze)) {System.out.println(maze);}System.out.println(maze);}}enum 指南针{东(1,0),西(-1,0),南(0,1),北(0,-1);int x,y;private 指南针(int x, int y) {this.x = x ;this.y = y;}public Point 走(Point point){point.translate(x, y);return point;}}package com.mao.user;import java.awt.Point;import java.util.HashMap;import java.util.Map;public class 迷宫 {public static final int INITMAZ = -1;Map<Point, Integer> 格子 = new HashMap<Point, Integer>();private int 面包屑 = 1;private int 边长 = 0 ;/** * 初始化迷宫 * @param 边长 */public 迷宫(int 边长){this.边长 = 边长;for(int i =0 ; i <边长*边长;i++){格子.put(new Point(i/边长,i%边长), INITMAZ);}}/** * 打印迷宫状态 */@Overridepublic String toString() {StringBuilder builder = new StringBuilder();for(int i =0 ; i <边长;i++){for(int j = 0 ; j < 边长 ; j ++){Integer show = 格子.get(new Point(j,i));builder.append(show);builder.append("\t");}builder.append("\n");}return builder.toString();}/** * 标记已走过的位置 * @param 位置 */public void 撒面包(Point 位置) {格子.put(位置,面包屑++);}/** * 这个点不在数组之中 * @param point * @return */public boolean 掉下悬崖(Point point) {if(point.x>=边长)return true;if(point.x<0)return true;if(point.y>=边长)return true;if(point.y<0)return true;return false;}/** * 这个点已经被标记过 * @param point * @return */public boolean 巨石压死(Point point) {if(格子.get(point)!=INITMAZ){return true;}return false;}}public class LostGirl {public Point point = new Point();public Compass compass = Compass.东; //初方向public int noWay = 0 ;public int walk(Maze maze){if(noWay==0){maze.breadRoad(point);//如果不是退回来的话就要作记号}compass.run(point);if(maze.fallDown(point)||maze.crushedRock(point)){compass.back(point);//原路退回noWay++;//前方是死路一条compass=compass.next();//换个方向}else{noWay=0;}return noWay;}public static void main(String[] args) {Maze maze = new Maze(3);LostGirl girl = new LostGirl();while (girl.walk(maze) < 4) {//System.out.println(maze); //偷窥路线}System.out.println(maze);}}enum Compass{东(1,0){public Compass next(){return 南;}},南(0,1){public Compass next(){return 西;}},西(-1,0){public Compass next(){return 北;}},北(0,-1){public Compass next(){return 东;}};int x,y;private Compass(int x, int y) {this.x = x ;this.y = y;}public void back(Point point) {point.translate(-x, -y);}public void run(Point point){point.translate(x, y);}abstract Compass next();}public class Maze {Map<Point, Integer> map = new HashMap<Point, Integer>();private int bread = 1;private int length = 0 ;/** * 初始化迷宫 * @param length */public Maze(int length){this.length = length;}/** * 标记已走过的位置 * @param point */public void breadRoad(Point point) {map.put(new Point(point),bread++);}/** * 这个点不在数组之中 * @param point * @return */public boolean fallDown(Point point) {return (point.x>=length||point.x<0||point.y>=length||point.y<0);}/** * 这个点已经被标记过 * @param point * @return */public boolean crushedRock(Point point) { return map.get(point)!= null ;}/** * 打印迷宫状态 */@Overridepublic String toString() {StringBuilder builder = new StringBuilder();for(int i =0 ; i <length;i++){for(int j = 0 ; j < length ; j ++){Integer show = map.get(new Point(j,i));builder.append(show);builder.append("\t");}builder.append("\n");}return builder.toString();}}# coding: utf-8require 'matrix'def 诱 数 妹, 鼠 = Vector[0,0], Vector[0,1] 抓 = Matrix[[0,1],[-1,0]] # 正经点说: 这个是旋转矩阵 摸 = [] (0...数).each{|位| 摸[位] = Array.new 数, '纯洁'} 1.upto(数 * 数){|吃| 女, 未 = 妹.to_a 摸[女][未] = 吃 排, 雷 = (妹 + 鼠).to_a 里 = (排 >= 0 and 排 < 数 and 雷 >= 0 and 雷 < 数) 鼠 = 抓 * 鼠 unless (里 and 摸[排][雷] == '纯洁') # 鼠死重抓 妹 += 鼠 } 齐 = (数 * 数).to_s.size puts "英特 爱=#{数};".encode(Encoding.default_external) rescue nil puts 摸.map{|行| 行.map{|粒| 粒.to_s.ljust 齐}.join ' '}.join("\n")end诱 5诱 6