小程序-走迷宫
遇到一个关于走迷宫的小题目,对于一直做JAVAEE的开发者,这还是头一招。
如图:
白色格子:表示可以走
黑色格子:表示不能走
如何用程序来实现从左上角走到右下角?并且程序给出行走路径?
我的思路(如果有更好的思路,可以联系我[email protected]):
1.给表格加坐标
2.怎么走?每走到一步,检查这一步的上下左右四个格子是否可以走:如果可以,就继续下一步,并且记录之前走的路径
3.要用到递归
好了,上代码:
首先定义每个格子是一个对象:MiGongItem(楼主读书少,拼音和英文混动。。。)
package com.xiaobin.migong; import java.util.ArrayList; import java.util.List; public class MiGongItem { private int xAxis; private int yAxis; private boolean avalialbe = false;//是否可以走 private boolean isFrom = false;//是否是从这里出发的 public List<MiGongItem> roadList = new ArrayList<MiGongItem>(); public int getxAxis() { return xAxis; } public void setxAxis(int xAxis) { this.xAxis = xAxis; } public int getyAxis() { return yAxis; } public void setyAxis(int yAxis) { this.yAxis = yAxis; } public boolean isAvalialbe() { return avalialbe; } public void setAvalialbe(boolean avalialbe) { this.avalialbe = avalialbe; } public boolean isFrom() { return isFrom; } public void setFrom(boolean isFrom) { this.isFrom = isFrom; } public List<MiGongItem> getRoadList() { return roadList; } public void setRoadList(List<MiGongItem> roadList) { this.roadList = roadList; } public String getKey(){ return xAxis+","+yAxis; } }
再就是定义一个Test的类
包括生成数据
定义递归方法
输出路径
package com.xiaobin.migong; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; public class MiGongTest { private static Map<String, MiGongItem> data = new HashMap<String, MiGongItem>(); static{ generateData(); } public static void main(String[] args) { MiGongItem start = data.get("1,1"); List<MiGongItem> list = new ArrayList<MiGongItem>(); list.add(start); List<MiGongItem> result = null; while(true){ result = getAvailables(list); if(result==null || result.isEmpty()){ System.out.println("Find Way Out..."); for(MiGongItem it:list){ for(MiGongItem item:it.roadList){ System.out.print("["+item.getKey()+"]-"); } System.out.println("["+it.getKey()+"]"); } break; } list = result; } } public static List<MiGongItem> getAvailables(List<MiGongItem> list){ if(list==null || list.size()==0){ System.out.println("no from items"); return null; } List<MiGongItem> availables = new ArrayList<MiGongItem>(); for(MiGongItem item:list){ int x = item.getxAxis(); int y = item.getyAxis(); item.setFrom(true); MiGongItem upItem = data.get(x+","+(y-1)); MiGongItem downItem = data.get(x+","+(y+1)); MiGongItem leftItem = data.get((x-1)+","+y); MiGongItem rightItem = data.get((x+1)+","+y); if(upItem!=null && !upItem.isFrom() && upItem.isAvalialbe()){ upItem.roadList.addAll(item.roadList); upItem.roadList.add(item); availables.add(upItem); } if(downItem!=null && !downItem.isFrom() && downItem.isAvalialbe()){ downItem.roadList.addAll(item.roadList); downItem.roadList.add(item); availables.add(downItem); } if(leftItem!=null && !leftItem.isFrom() && leftItem.isAvalialbe()){ leftItem.roadList.addAll(item.roadList); leftItem.roadList.add(item); availables.add(leftItem); } if(rightItem!=null && !rightItem.isFrom() && rightItem.isAvalialbe()){ rightItem.roadList.addAll(item.roadList); rightItem.roadList.add(item); availables.add(rightItem); } } return availables; } public static void generateData(){ MiGongItem item = null; /////////1 item = new MiGongItem(); item.setxAxis(1); item.setyAxis(1); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(1); item.setyAxis(2); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(1); item.setyAxis(3); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(1); item.setyAxis(4); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(1); item.setyAxis(5); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(1); item.setyAxis(6); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); /////////2 item = new MiGongItem(); item.setxAxis(2); item.setyAxis(1); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(2); item.setyAxis(2); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(2); item.setyAxis(3); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(2); item.setyAxis(4); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(2); item.setyAxis(5); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(2); item.setyAxis(6); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); /////////3 item = new MiGongItem(); item.setxAxis(3); item.setyAxis(1); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(3); item.setyAxis(2); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(3); item.setyAxis(3); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(3); item.setyAxis(4); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(3); item.setyAxis(5); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(3); item.setyAxis(6); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); /////////4 item = new MiGongItem(); item.setxAxis(4); item.setyAxis(1); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(4); item.setyAxis(2); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(4); item.setyAxis(3); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(4); item.setyAxis(4); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(4); item.setyAxis(5); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(4); item.setyAxis(6); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); /////////5 item = new MiGongItem(); item.setxAxis(5); item.setyAxis(1); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(5); item.setyAxis(2); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(5); item.setyAxis(3); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(5); item.setyAxis(4); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(5); item.setyAxis(5); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(5); item.setyAxis(6); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); /////////6 item = new MiGongItem(); item.setxAxis(6); item.setyAxis(1); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(6); item.setyAxis(2); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(6); item.setyAxis(3); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(6); item.setyAxis(4); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(6); item.setyAxis(5); item.setFrom(false); item.setAvalialbe(false); data.put(item.getKey(), item); item = new MiGongItem(); item.setxAxis(6); item.setyAxis(6); item.setFrom(false); item.setAvalialbe(true); data.put(item.getKey(), item); } }
好了,就这么多了
高手轻喷。。