`
抛出异常的爱
  • 浏览: 629142 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

从前有个迷宫__面试题

阅读更多
所有的代码不包括测试.
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;
	}

}


分享到:
评论
16 楼 fengsky491 2009-12-15  
占楼,有时间再看
15 楼 抛出异常的爱 2009-12-15  
刑天战士 写道
lz是否面试的无限讯奇?

参考一下这里.
http://www.iteye.com/topic/545378
PS:这里有很多人写的答案非常的牛.
14 楼 抛出异常的爱 2009-12-15  
mathfox 写道
怎么看汉字变量,头这么晕呢。

我感冒又严重了?

面包=bread
指南针=compass
迷宫=maze

这些中文看着不爽
写着也不爽
eclipse
对输入法不提供代码提示.......

平时是不写中文变量名的.
13 楼 mathfox 2009-12-15  
怎么看汉字变量,头这么晕呢。

我感冒又严重了?
12 楼 刑天战士 2009-12-15  
lz是否面试的无限讯奇?
11 楼 抛出异常的爱 2009-12-15  
风之旋律 写道
这是面试题.......

要是这么作面试题....
我估计老板是不会要的.
1.这题考的是递归.
没用递归写不会满分.

2.这个是用测试先行方式作的
没ide那死吧.....
这个过程中出了四次错误.
一次逻辑严重失误
如果没用测试开发,
每个bug要用1小时来找bug

我是没信心一次写对这么长的东西

weixla 写道
标准的OO

3.写这个只是图一乐.
如果我面试作这题的话.
估计与其它几个面条写的也差不多.
10 楼 weixla 2009-12-15  
标准的OO
9 楼 风之旋律 2009-12-15  
这是面试题.......
8 楼 ansjsun 2009-12-15  
沙发..占了再说
7 楼 抛出异常的爱 2009-12-15  
不幸的小女孩终于被老鼠带到了哪也去不了的绝境......

王子变成的老鼠在旁边嘿嘿的笑着.
引用

1 -1 -1
-1 -1 -1
-1 -1 -1

1 2 -1
-1 -1 -1
-1 -1 -1

1 2 3
-1 -1 -1
-1 -1 -1

1 2 3
-1 -1 4
-1 -1 -1

1 2 3
-1 -1 4
-1 -1 5

1 2 3
-1 -1 4
-1 6 5

1 2 3
-1 -1 4
7 6 5

1 2 3
8 -1 4
7 6 5

1 2 3
8 9 4
7 6 5
6 楼 抛出异常的爱 2009-12-15  
每天早晨小女孩吃过面包之后
就抓老鼠.
让老鼠向四个方向探路
她坚持向着同一个方向走.
当然如果这个方向不能走了就随便找一个方向走
如果没有路了天真小白一点也没想过.
	@Test
	public void test有很多路但我们直走() {
		小白.set位置(new Point(0,0));
		
		maze = new 迷宫(2);
		小白.走一步(maze);
		assertEquals(new Point(1,0), 小白.get位置());
		

	}
	@Test
	public void test不能直走我们换方向() {
		小白.set位置(new Point(1,0));
		maze = new 迷宫(2);
		maze.撒面包(new  Point(0,0));
		小白.走一步(maze);
		assertEquals(new Point(1,1), 小白.get位置());
		小白.走一步(maze);
		assertEquals(new Point(0,1), 小白.get位置());
		
		assertTrue(小白.走一步(maze));

	}

	public boolean 走一步(迷宫 maze){
		maze.撒面包(位置);
		List<指南针> ways = findWayOut(maze);
		if(ways.isEmpty()){
			return true;
		}else if(ways.contains(方向)){
			方向.走(位置);
		}else{
			ways.iterator().next().走(位置);
		}
		return false;
	}


5 楼 抛出异常的爱 2009-12-15  
小女孩想了想说
小老鼠,你愿意不愿意为了我去呢?
..............
那样你顺这个方向跑如果没危险就回来告诉我.
	@Test
	public void test找路() {
		小白.set位置(new Point(0,0));
		maze = new 迷宫(2);
		List list = 小白.findWayOut(maze);
		assertNotNull(list);
		assertFalse(list.isEmpty());
		assertEquals(2, list.size() );
	}

	public List<指南针> findWayOut(迷宫 maze){
		List<指南针> ways = new ArrayList<指南针>();
		for(指南针 way:指南针.values()){
			Point rate = new Point(位置);
			way.走(rate);
			if(maze.掉下悬崖(rate)){
			   //听到惨叫声越来越远....
			}else if(maze.巨石压死(rate)){
			  //听到轰的一声心里祈祷老鼠能平安无事....
			}else{
				ways.add(way);//
			}
		}
		return ways;
	}


4 楼 抛出异常的爱 2009-12-15  
这时小老鼠说话了:
迷宫的边缘是悬崖,
如果走了相同的格子会被巨石压死
	@Test
	public void test掉下悬崖() {
		方盒子 = new 迷宫(2);
		assertEquals(true, 方盒子.掉下悬崖(new Point(0,11)));
	}
	@Test
	public void test巨石压死() {
		方盒子 = new 迷宫(2);
		assertEquals(false, 方盒子.巨石压死(new Point(0,0)));
		方盒子.撒面包(new Point(0,0));
		assertEquals(true, 方盒子.巨石压死(new Point(0,0)));
	}
	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;
	}
	public boolean 巨石压死(Point point) {
		if(格子.get(point)!=INITMAZ){
			return true;
		}
		return false;
	}
	

3 楼 抛出异常的爱 2009-12-15  
迷宫多大啊会不会迷路?
一只老鼠拖着面包走过.
小女孩一把抓住了老鼠
缴获了面包.
她想如果把面包屑洒到来时的路上
就不会迷路了.
public class 迷路小女孩 {
	private Point  位置;
	private 指南针 方向;
	public Point get位置() {
		return 位置;
	}

	public void set位置(Point 位置) {
		this.位置 = 位置;
	}
	public boolean 走一步(迷宫 maze){
		maze.撒面包(位置);
		return false;
	}
}
enum 指南针{
	东,西,南,北;
}

//测试
	@Test
	public void test撒面包() {
		方盒子 = new 迷宫(2);
		方盒子.撒面包(new Point(0,0));
		assertNotSame(迷宫.INITMAZ, 方盒子.格子.get(new Point(0,0)));
	}
	@Test
	public void test撒面包会自增涨() {
		方盒子 = new 迷宫(2);
		方盒子.撒面包(new Point(0,0));
		方盒子.撒面包(new Point(0,1));
		assertEquals(2, 方盒子.格子.get(new Point(0,1)));//二次就增涨为2
	}


public class 迷宫 {
	public static final int INITMAZ = -1;
	Map<Point, Integer> 格子 = new HashMap<Point, Integer>();
	private int 面包屑 = 1;
	private int 边长 = 0 ;
	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();
	}

	public void 撒面包(Point 位置) {
		
		格子.put(位置,面包屑++);
	}

}


每走一步位置都要变化

public class 迷路小女孩Test {
	迷路小女孩 小白 ;
	迷宫 maze;
	@BeforeClass
	public static void setUpBeforeClass() throws Exception {
	}

	@Before
	public void setUp() throws Exception {
		小白 = new 迷路小女孩();
		maze = new 迷宫(2);
	}

	@After
	public void tearDown() throws Exception {
	}

	@Test
	public void test走一步撒些面包() {
		小白.set位置(new Point(0,0));
		assertEquals(maze.INITMAZ,maze.格子.get(new Point(0,0)));
		小白.走一步(maze);
		assertNotSame(maze.INITMAZ,maze.格子.get(new Point(0,0)));
	}
	@Test
	public void test走一步位置变化() {
		小白.set位置(new Point(0,0));
		小白.走一步(maze);
		assertEquals(new Point(1,0),小白.get位置());
		小白.走一步(maze);
		assertEquals(new Point(2,0),小白.get位置());
	}

}


手拿指南针.就可以知道向哪个方向走了
public class 迷路小女孩 {
	private Point  位置;
	private 指南针 方向 = 指南针.东;//初方向
	public Point get位置() {
		return 位置;
	}

	public void set位置(Point 位置) {
		this.位置 = 位置;
	}
	public boolean 走一步(迷宫 maze){
		maze.撒面包(位置);
		
		方向.走(位置);
		return false;
	}
}
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;
	}
}

2 楼 抛出异常的爱 2009-12-15  
巫师抓了个小女孩放到迷宫里.

public class 迷路小女孩 {
	private Point  位置;

	public Point get位置() {
		return 位置;
	}

	public void set位置(Point 位置) {
		this.位置 = 位置;
	}
	

}

小女孩找到了好心王子偷偷放进迷宫的指南针
public class 迷路小女孩 {
	private Point  位置;
        private 指南针 方向;
	public Point get位置() {
		return 位置;
	}

	public void set位置(Point 位置) {
		this.位置 = 位置;
	}
}
enum 指南针{
	东,西,南,北;
}


小女孩 小心翼翼的上路了
public class 迷路小女孩 {
	private Point  位置;
	private 指南针 方向;
	public Point get位置() {
		return 位置;
	}

	public void set位置(Point 位置) {
		this.位置 = 位置;
	}
	public boolean 走一步(迷宫 maze){
		return false;
	}
}
enum 指南针{
	东,西,南,北;
}

1 楼 抛出异常的爱 2009-12-15  
从前有个魔法迷宫
public class 迷宫 {
	Map<Point, Integer> 格子 = new HashMap<Point, Integer>();
}

只要念个咒语它就会出现.
public class 迷宫 {
	Map<Point, Integer> 格子 = new HashMap<Point, Integer>();
	public 迷宫(int 边长){
		
	}


}

/**
    测试
*/
public class 迷宫Test {
	迷宫 方盒子;
	@BeforeClass
	public static void setUpBeforeClass() throws Exception {
	}

	@Before
	public void setUp() throws Exception {
	}

	@After
	public void tearDown() throws Exception {
	}

	@Test
	public void test迷宫() {
		方盒子 = new 迷宫(3);
		assertEquals(方盒子.格子.isEmpty(),false);
	}

}

变态巫师监视成瘾....
制作了toString...
用来偷窥迷宫中的动静.
public class 迷宫 {
	public static final int INITMAZ = -1;
	Map<Point, Integer> 格子 = new HashMap<Point, Integer>();
	private int 边长 = 0 ;
	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();
	}

}
public class 迷宫Test {
	迷宫 方盒子;
	@BeforeClass
	public static void setUpBeforeClass() throws Exception {
	}

	@Before
	public void setUp() throws Exception {
	}

	@After
	public void tearDown() throws Exception {
	}

	@Test
	public void test迷宫() {
		方盒子 = new 迷宫(3);
		assertEquals(方盒子.格子.isEmpty(),false);
	}
	/**
	 * 
	 */
	@Test
	public void test迷宫大小() {
		方盒子 = new 迷宫(3);
		assertEquals(方盒子.格子.size(),9);
		
	}
	@Test
	public void testToString() {
		方盒子 = new 迷宫(2);
		StringBuilder builder = new StringBuilder();
		builder.append("-1\t-1\t");
		builder.append("\n");
		builder.append("-1\t-1\t");
		builder.append("\n");
		assertEquals(方盒子.toString(),builder.toString());
		System.out.println(方盒子);//邪恶的监视者
	}

}

相关推荐

    migong.zip_qt 迷宫_qt走迷宫_qt迷宫_迷宫 QT_迷宫 qt代码

    在“migong.zip_qt 迷宫_qt走迷宫_qt迷宫_迷宫 QT_迷宫 qt代码”这个压缩包中,我们可以看到一个使用QT库创建的迷宫游戏项目。这个项目不仅展示了QT的基本用法,还涉及到了算法设计、游戏逻辑和用户交互等方面的知识...

    走迷宫_算法、走迷宫_

    有一个N*M的格子迷宫,1代表该格子为墙,不能通过,0代表可以通过,另外,在迷宫中有一些传送门,走到传送门的入口即会自动被传送到传送门的出口(一次传送算1步)。人在迷宫中可以尝试上下左右四个方向移动。现在...

    mg.rar_asm 游戏_asm迷宫_汇编 迷宫_汇编 迷宫游戏_汇编小游戏

    总之,《mg.rar_asm 游戏_asm迷宫_汇编 迷宫_汇编 迷宫游戏_汇编小游戏》是一个展示汇编语言在游戏开发中独特应用的实例,它揭示了底层编程的魅力和挑战,对于想要深入了解计算机硬件和程序执行原理的爱好者来说,是...

    迷宫一个走迷宫的程序.rar_迷宫_迷宫 C++_迷宫 代码

    标题中的“迷宫一个走迷宫的程序.rar”暗示了这是一个关于使用C++编程语言实现的迷宫解决方案的项目。这个程序可能包含了算法设计、数据结构应用以及基本的编程概念,如循环、条件语句和函数。迷宫问题在计算机科学...

    migong.rar_c 迷宫_visual c_自动生成迷宫_迷宫求解

    在计算机科学领域,迷宫生成与求解是一个经典的问题,它涉及到图论、算法设计与分析等多个知识点。本项目“migong.rar_c 迷宫_visual c_自动生成迷宫_迷宫求解”就是针对这一主题进行深入探讨的实例,主要使用了C++...

    Maze_qt迷宫_迷宫qt代码_qt生成迷宫_QT游戏_Qt;C++;迷宫;游戏_

    同时,为了适应不同大小的迷宫,程序需要有自适应布局的设计,这通常通过Qt的QLayout和QGridLayout来实现。 自动计算通关路径的功能,可能运用了回溯法或者A*寻路算法。回溯法从起点开始,尝试探索所有可能的路径,...

    zoumigong.rar_老鼠形象_老鼠走迷宫_老鼠迷宫游戏_迷宫图_迷宫老鼠游戏

    程序开始运行时显示一个迷宫地图,迷宫中央有一只老鼠,迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。 要求: 1老鼠形象可辨认,可用键盘操纵老鼠上下左右移动; 2...

    迷宫_C#游戏_迷宫_自动寻路_

    在本文中,我们将深入探讨如何使用C#编程语言来创建一个迷宫游戏,并实现自动寻路功能。C#是一种广泛应用于开发桌面应用、游戏、移动应用以及Web应用的强大语言,其丰富的类库和面向对象的特性使其非常适合进行游戏...

    迷宫_迷宫_源码.zip

    《迷宫_迷宫_源码.zip》是一个包含迷宫算法和实现的源代码压缩包。迷宫问题在计算机科学中是一个经典的算法挑战,通常涉及路径寻找、图论和搜索算法。在这里,我们将深入探讨迷宫算法的核心概念、常见的解决策略以及...

    Maze迷宫游戏_迷宫小游戏C++_迷宫_

    在本文中,我们将深入探讨如何使用C++编程语言来实现一个经典的迷宫游戏。迷宫游戏是一种极具挑战性和趣味性的智力活动,它涉及到路径搜索、决策制定和算法应用。在这个项目中,我们将创建一个名为“小老鼠走迷宫”...

    迷宫_迷宫_源码

    解决这个问题的核心算法有多种,包括深度优先搜索(DFS)、广度优先搜索(BFS)以及A*搜索等。 1. **深度优先搜索(DFS)**:DFS是一种递归的搜索策略,它尽可能深地探索迷宫的分支。在每个节点,它都会尝试走一条...

    Java编写的求解迷宫问题的小程序.zip_Java 迷宫_java小程序_java迷宫_迷宫java_迷宫问题

    这个压缩包文件包含了一个使用Java语言编写的解决迷宫问题的小程序。让我们深入探讨一下这个程序可能涉及的Java编程知识和迷宫问题的解决策略。 首先,Java是一种面向对象的编程语言,它提供了丰富的类库和强大的...

    maz.rar_maz _最短路径 c_迷宫_迷宫 C++

    在本文中,我们将深入探讨如何使用C++编程语言来实现一个迷宫求解器,它不仅能够找到从起点到终点的路径,而且还能找到最短路径。这个项目名为"maz.rar_maz _最短路径 c_迷宫_迷宫 C++",包含了相关的源代码和文档。...

    c++代码实现走迷宫.rar_C++_c++实现走迷宫_maze_编程走迷宫_走迷宫 C++

    这个项目通过C++语言实现了走迷宫的功能,让用户能够设计并解决各种迷宫问题。下面将详细介绍这个主题涉及的知识点。 首先,我们需要理解迷宫问题的基本概念。一个迷宫通常被表示为二维矩阵或图,其中每个节点代表...

    main_迷宫_迷宫求解_源码

    在IT领域,迷宫求解是一个经典的算法问题,它涉及到路径搜索、图论以及最优化策略。本项目名为"main_迷宫_迷宫求解_源码",其核心目标是通过编程来找到给定迷宫矩阵中最短的出路。下面我们将详细探讨迷宫求解的原理...

    迷宫问题_return_迷宫问题_迷宫_数据结构_

    用C++语言实现在迷宫中寻找出路。核心算法伪代码:do{如果当前位置为出口: 当前位置进栈;return 1;while(尝试的方向小于4){尝试方向号码对应方向的格子;如果这个格子是没走过的通路: 当前位置进栈; 将地图上...

    migong.rar_migong_数据结构 迷宫_栈的应用_迷宫 栈_迷宫问题

    标题中的“migong.rar_migong_数据结构 迷宫_栈的应用_迷宫 栈_迷宫问题”暗示了这是一个关于使用栈解决迷宫问题的案例。迷宫问题通常涉及到寻找从起点到终点的有效路径,而栈在这里起到了记录和回溯路径的作用。 ...

    找到一个给定的迷宫最短路径.zip_matlab 迷宫路径_matlab走迷宫_最短路径_用matlab走迷宫_迷宫最短路径

    在matlab虚拟环境,找到迷宫的最短路径

    迷宫游戏.rar_C++_c++ prim迷宫_passagev99_prim迷宫_prim迷宫 c++

    C++编写的迷宫游戏,利用随机prim算法生成迷宫

    迷宫_exchangeiqq_Vc_

    【标题】"迷宫_exchangeiqq_Vc_"指的...总的来说,"迷宫_exchangeiqq_Vc_"项目是一个综合性的C++编程实践,涵盖了数据结构、算法、输入输出处理、用户界面设计等多个方面,对提升C++编程技能和理解游戏逻辑有很大帮助。

Global site tag (gtag.js) - Google Analytics