从前有个迷宫__面试题

所有的代码不包括测试.

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);
		}
	}
	/**
	 * 打印迷宫状态
	 */
	@Override
	public 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;
	}

}

评论

36 楼 hevowish 2010-11-17  

一个故事 + OO + 测试先行，描述转圈打印的算法，抛哥费心了。

35 楼 抛出异常的爱 2010-11-10  

tyzqqq 写道

这个写的有很多面向对象特征，不过用循环回溯更体现算法的思想，而且更简洁直观，因为这种题相当于一个小功能而不是一个功能模块。开发中也这样做吗？

算法的好处是你只需要写出最好的.....就可以
但事实上现实中代码是在不得的变化的
需求也在变化.
数据结构也在变化.

看看我指南针的写法变化....

面向对象不过是一屏写不下的情况下
没什么人可以全局把握代码.

分成多个元素每个元素
每个元素内的代码可以自解释.

34 楼 tyzqqq 2010-11-10  

这个写的有很多面向对象特征，不过用循环回溯更体现算法的思想，而且更简洁直观，因为这种题相当于一个小功能而不是一个功能模块。开发中也这样做吗？

33 楼 yfnok 2010-11-09  

什麼啊？這麼複雜的面試題，他以為他是微軟！？

32 楼 chenyuxiaoxiao 2010-10-09  

为发扬抛哥的精神 小弟写了一个2维数组的迷宫版本 向大家请教 下面是我写的原创的地址
原创地址：http://chenyuxiaoxiao.iteye.com/blog/779322

import java.util.Arrays;
import java.util.Scanner;

public class Migong {

	/**
	 * 求迷宫的打印方法
	 * 01 02 03 04 05   00 01 02 03 04   5 4 4 3 3 2 2 1 1 //5阶迷宫每转一次湾 就要走的步数
	 * 16 17 18 19 06   10 11 12 13 14   4 3 3 2 2 1 1 //4阶迷宫每转一次湾 就要走的步数

	 * 15 24 25 20 07   20 21 22 23 24   3 2 2 1 1 //3阶迷宫每转一次湾 就要走的步数

	 * 14 23 22 21 08   30 31 32 33 34   2 1 1//2阶迷宫每转一次湾 就要走的步数

	 * 13 12 11 10 09   40 41 42 43 44   1//1阶迷宫每转一次湾 就要走的步数

	 */
	private static String[][] migong;
	private static Integer n;
	private static enum direct {
		left,right,up,down
	}
	public static void main(String[] args) {
		System.out.print("请输入迷宫的阶数：");
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		init_migong(n);
		//第一次走n 步  以后每两次转弯少走一步
		int step = n;
		int num = 1;
		int heng = 0; //横坐标
		int zong = 0; //纵坐标
		int upwan = 0;
		int leftwan = 0;
		//走的次数为  2 * n -1
		for(int i = 0 ;i<(2 * n -1);i++){
			String dir = next(i);
			if(dir.equals("right")){
				if(i==0){
					zong = 0;
				}else{
					zong = zong + 1;
				}
				for(int j = 1;j<= (step);j++){
					migong[heng][zong] = add_zero(num);
					zong++;
					num++;
				}
			}else if(dir.equals("down")){
				heng = heng + 1;
				zong = zong -1;
				for(int j = 1;j<= step;j++){
					migong[heng][zong] = add_zero(num);
					heng++;
					num++;
				}
			}else if(dir.equals("left")){
				heng = heng -1;
				zong = zong -1;
				for(int j = step;j>=1;j--){
					migong[heng][zong] = add_zero(num);
					zong--;
					if(1 == j){
						zong = leftwan;
					}
					num++;
				}
				leftwan = leftwan +1;
			}else if(dir.equals("up")){
				upwan = upwan +1;
				heng = heng -1;
				for(int j = step;j>=1;j--){
					migong[heng][zong] = add_zero(num);
					heng--;
					if(1 == j){
						heng = upwan;
					}
					num++;
				}
			}
			if(i%2==0){
				step = step -1;
			}
		}
		printmigong();
	}

	private static String next(int i){
		int mod = i % 4;
		String dir = "left";
		switch (mod) {
		case 0:
			dir = direct.right.toString();
			break;
		case 1:
			dir = direct.down.toString();
			break;
		case 2:
			dir = direct.left.toString();
			break;
		case 3:
			dir = direct.up.toString();
			break;
		}
		return dir;
	}
	private static String add_zero(Integer num){
		Integer temp = n * n;
		String s = temp.toString(); 
		Integer len = s.length();
		Integer l = num.toString().length();
		String zero = "";
		for(int i = 1;i<=len -l;i++ ){
			zero = zero + "0";
		}
		return zero + num; 
	}
	private static void printmigong(){
		for(int i = 0 ;i<migong.length;i++){
			System.out.println(Arrays.toString(migong[i]));
		}
	}
	private static void init_migong(Integer n) {
		migong = new String[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				migong[i][j] = "-1";
			}
		}
	}
}

31 楼 wkzhjz 2010-08-04  

占个座位回头看

30 楼 抛出异常的爱 2010-04-03  

又重写Compass
next循环模式
变态模式
如有用到。。。。
请自行重构到能看懂再用。

return values()[((ordinal()+1)%(values().length))];

enum Compass{
	东(1,0),南(0,1),西(-1,0),北(0,-1);	
	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);
	}
        public Compass next(){
    	    return values()[((ordinal()+1)%(values().length))];
        }

}

29 楼 抛出异常的爱 2009-12-31  

又重写Compass
next循环解决了

enum Compass{
	东(1,0),南(0,1),西(-1,0),北(0,-1);	
	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);
	}
	public static Compass next(Compass compass){
		Iterator<Compass> it = new LoopingIterator(EnumSet.allOf(Compass.class));
		while(!compass.equals(it.next())){}		
		return it.next();
	}

}

28 楼 刑天战士 2009-12-25  

supersun 写道

刑天战士 写道

lz是否面试的无限讯奇？

无限讯奇面试题不是这样的，话说哪天去那面试，还真看见不少MM

部门和部门之前不一样的，我是基础技术部，你面的哪个？基础技术部和搜索部对技术要求很高。我面试的时候被5个人LJ……

27 楼 q530414675 2009-12-24  

讲得狠详细,,看下可能会用到!

26 楼 supersun 2009-12-17  

刑天战士 写道

lz是否面试的无限讯奇？

无限讯奇面试题不是这样的，话说哪天去那面试，还真看见不少MM

25 楼 东四环屠夫 2009-12-17  

我对他们的回复很不满：不仅代码表意不清，而且没有好好的对齐打印。
依据抛哥的指导思想，写了 Ruby 版：

# coding: utf-8
require '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

24 楼 抛出异常的爱 2009-12-17  

jenlp520 写道

我不DJ的补充下

抛抛把girl都拼成了gril  

好吧我重构一下再看看
代码不是很多了.

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);
		
		
	}

}

手写了next函数
我认为这个应该在api中有....

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 ;
	}
	/**
	 * 打印迷宫状态
	 */
	@Override
	public 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();
	}
}

23 楼 jenlp520 2009-12-17  

我不DJ的补充下

抛抛把girl都拼成了gril  

22 楼 wgh-23 2009-12-16  

又看到这个朴素的头像了，呵呵……

21 楼 抛出异常的爱 2009-12-16  

写这个程序时最大的遗憾是:
enum
类型中的元素没有next方法.
只能自己手动的加上.....
好失败啊.

我写这东西主要目的
是为了让人看的明白

记的住

20 楼 sxpyrgz 2009-12-16  

[
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]
]
1是小女孩儿

19 楼 yuyanshan 2009-12-15  

真是小牛撞见大牛了，P服。

18 楼 xuzhu200008 2009-12-15  

大牛出动了，崇拜一下！

17 楼 flyfan 2009-12-15  

我英文很烂，但看到这里的中文更晕，原来英文这么优雅