小程序-走迷宫

遇到一个关于走迷宫的小题目，对于一直做JAVAEE的开发者，这还是头一招。

如图：

小程序-走迷宫

白色格子：表示可以走

黑色格子：表示不能走

如何用程序来实现从左上角走到右下角？并且程序给出行走路径？

我的思路（如果有更好的思路，可以联系我179634696@qq.com）：

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

}

View Code

小程序-走迷宫

相关推荐