|
锁定老帖子 主题：从前有个迷宫__面试题
精华帖 (6) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-12-15
最后修改：2009-12-15
所有的代码不包括测试.
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;
}
}
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2009-12-15
最后修改：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(方盒子);//邪恶的监视者
}
}
|
| 返回顶楼 | |
|
发表时间：2009-12-15
最后修改：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 指南针{
东,西,南,北;
}
|
| 返回顶楼 | |
|
发表时间：2009-12-15
最后修改：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;
}
}
|
| 返回顶楼 | |
|
发表时间：2009-12-15
最后修改：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;
}
|
| 返回顶楼 | |
|
发表时间：2009-12-15
最后修改：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;
}
|
| 返回顶楼 | |
|
发表时间：2009-12-15
最后修改：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;
}
|
| 返回顶楼 | |
|
发表时间：2009-12-15
最后修改：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 |
| 返回顶楼 | |
|
发表时间：2009-12-15
沙发..占了再说
|
| 返回顶楼 | |
|
发表时间：2009-12-15
这是面试题.......
|
| 返回顶楼 | |
