抛出异常的爱
- 浏览: 620648 次
- 性别:
- 来自: 北京
-
最新评论
所有的代码不包括测试.
算法的好处是你只需要写出最好的.....就可以
但事实上现实中代码是在不得的变化的
需求也在变化.
数据结构也在变化.
看看我指南针的写法变化....
面向对象不过是一屏写不下的情况下
没什么人可以全局把握代码.
分成多个元素每个元素
每个元素内的代码可以自解释.
又重写Compass
next循环解决了
无限讯奇面试题不是这样的，话说哪天去那面试，还真看见不少MM
部门和部门之前不一样的，我是基础技术部，你面的哪个？基础技术部和搜索部对技术要求很高。我面试的时候被5个人LJ……
无限讯奇面试题不是这样的，话说哪天去那面试，还真看见不少MM
好吧我重构一下再看看
代码不是很多了.
手写了next函数
我认为这个应该在api中有....
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
原创地址：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))];
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 版：
依据抛哥的指导思想，写了 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
抛抛把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
抛抛把girl都拼成了gril
22 楼
wgh-23
2009-12-16
又看到这个朴素的头像了，呵呵……
21 楼
抛出异常的爱
2009-12-16
写这个程序时最大的遗憾是:
enum
类型中的元素没有next方法.
只能自己手动的加上.....
好失败啊.
我写这东西主要目的
是为了让人看的明白
记的住
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是小女孩儿
[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
我英文很烂，但看到这里的中文更晕，原来英文这么优雅
发表评论
-
vlc 必要的参数
2021-08-31 17:18 0vlc.exe -vvv -Idummy "rt ... -
grafana+mysql 页面设计
2019-02-25 08:51 0前提 1。主要是SELECT 。 2。使用mysql ... -
测试用例到底怎么才值的写
2016-04-30 10:32 0有个方法是这样的 public function ... -
postman cookies登陆设置
2016-04-28 09:30 1995必须登陆才能测试的接口如何测试? 打开这个开关就可以共用coo ... -
将png 切成ios android能用的格式
2016-04-28 01:24 699由于要求不高找了个在线切图的工具 http://images. ... -
如何在原有系统中加入功能(一数据库)
2016-04-24 11:06 779第一步想办法把建表语句导入一powerdesginer ... -
php递归 格式化 数字类型
2016-04-20 12:35 754/** * 数字转日期递归 ... -
freemind 怎么处理成为word
2015-06-11 19:37 16写文章用freemind打了一个草稿. 先导出成为htm ... -
架构师之路（工欲善其事，必先利其器）纸牌屋
2014-03-27 06:48 0起因：小胖的一个征集实现过程 https://gist.git ... -
油猴对抗一般广告
2012-11-14 00:07 1842看小说 好多好多的广告是必然的.. 所以 去掉iframe 去 ... -
回答一些很有共性的东西
2011-02-24 21:24 5533我作软件第二第三年时 ... -
粗糙的object打印日志用....
2010-11-04 18:40 2135function logJquery(o){ ... -
拳皇连招
2010-09-29 13:46 2333从列表中找到录入的后N位 class KOFTest { ... -
一个activeX方法 刚刚发现
2010-09-14 19:14 1479解答:此题 http://www.iteye.com/prob ... -
[反例]超短代码,意义不明
2010-08-19 17:49 1529public String logout(HttpServl ... -
站读帝
2010-07-26 09:29 1273http://www.hudong.com/wiki/%E7% ... -
不要重复发明轮子
2010-07-06 17:20 2128一直以为不要重复发明轮子的意义很简单. 今天看了人件.... ... -
答复: 不用判断语句求俩数中的大（或者小）数
2010-05-31 12:55 2079跳大神也是一种艺术: public class MaxMin ... -
集合合并
2010-05-28 10:15 1913用于时间表的合并 时间段的合并工作. public cla ... -
删除重名的记录
2010-04-05 23:04 1900面试看到这种题。。。。。 我估计考官的正确答案有可能是错的 所 ...
相关推荐
有一个N*M的格子迷宫，1代表该格子为墙，不能通过，0代表可以通过，另外，在迷宫中有一些传送门，走到传送门的入口即会自动被传送到传送门的出口（一次传送算1步）。人在迷宫中可以尝试上下左右四个方向移动。现在...
迷宫_迷宫_源码.zip
程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向键操纵老鼠在规定的时间内走到粮仓处。 要求： 1老鼠形象可辨认，可用键盘操纵老鼠上下左右移动； 2...
设计并实现了一个指定迷宫入口和出口、搜索迷宫走出路径的程序。
QT编写的迷宫。随机生成迷宫。支持键盘上下左右操作，计时，墙变路路变墙。
用Qt C++框架开发的迷宫游戏，迷宫随机生成，可设置迷宫规模大小，可自动计算通关路径，按“w
迷宫程序_C语言_迷宫_源码.zip
C#编写的游戏，自动创建迷宫， 而且自动寻找迷宫的路径。
用C++语言实现在迷宫中寻找出路。核心算法伪代码：do{如果当前位置为出口： 当前位置进栈；return 1；while（尝试的方向小于4）{尝试方向号码对应方向的格子；如果这个格子是没走过的通路： 当前位置进栈； 将地图上...
在matlab虚拟环境，找到迷宫的最短路径
C编写的一个迷宫的源代码
C++编写的迷宫游戏，利用随机prim算法生成迷宫
迷宫问题，根据给定入口出口，找出到达的所有路径
利于c++完成对迷宫的编程设计，运行后成功走出迷宫
汇编语言完成的迷宫游戏，可以运行，可以再dos中玩这个小游戏
我实现了opengl下的3d迷宫，打开运行之后可以看到若干个贴有纹理的面片和地面，可以用键盘和鼠标控制旋转的方向，请在vs2015的环境下打开，需要提前配置好glut库
如果你要解决一个别人给的走迷宫的问题，同样还是要这样，首先把别人给的迷宫在计算机中表示出来，其次结合数据结构所学的知识，找到通路，（关于结合数据结构的知识就看你自己的了，关键是对堆栈的了解）。
小老鼠走迷宫，迷宫代码，使用C++完成，质量良好
迷宫求解，用栈来实现，深度搜索，自动生成迷宫。
这是一个基于python实现的生成随机迷宫算法核心代码分享