现在的位置: 首页 > 综合 > 正文

迷宫算法

2018年03月29日 ⁄ 综合 ⁄ 共 2657字 ⁄ 字号 小 中 大 ⁄ 评论关闭
  1. import java.util.Stack; 
  4. public class FindPath { 
  6.  private static final int wid = 8; 
  8.  private static final int hei = 8; 
  12.  private Stack stack = new Stack(); 
  13.  /** 
  14.   * @param args 
  15.   */ 
  16.  public static void main(String[] args) { 
  17.   // TODO Auto-generated method stub 
  18.   byte[] map = {1,1,1,1,1,1,1,1, 
  19.     1,1,1,1,0,1,1,1, 
  20.     1,0,0,1,0,0,1,1, 
  21.     1,0,0,0,0,0,1,1, 
  22.     1,1,0,0,1,1,1,1, 
  23.     1,1,1,0,1,1,1,1, 
  24.     1,1,0,0,1,1,1,1, 
  25.     1,1,1,1,1,1,1,1}; 
  26.   for (int i = 0; i < map.length; i++) { 
  27.    System.out.print(map[i] + " "); 
  28.    if (i % wid == wid - 1) { 
  29.     System.out.print("/n"); 
  30.    } 
  31.   } 
  32.   System.out.print("/n"); 
  33.   FindPath ai = new FindPath(); 
  34.   ai.find(map, 12, 50); 
  36.  } 
  39.  public void find(byte[] map, int origin, int target) { 
  40.   int[] step = new int[2]; 
  41.   step[1] = origin; 
  42.   stack.addElement(step); 
  43.   if(findPath(map,origin,target)){ 
  44.    System.out.println("succ"); 
  45.    for (int i = 0; i < stack.size(); i++) { 
  46.     int[] temp = (int[])stack.elementAt(i); 
  47.     System.out.println(i+" /t"+(char)temp[0]+" "+temp[1]); 
  48.    } 
  49.   }else{ 
  50.    System.out.println("fail"); 
  51.   } 
  52.  } 
  54.  /** 
  55.   * 在地图上找到从原点到目标位置的路径 
  56.   *  
  57.   * @param map 
  58.   * @param origin 
  59.   * @param target 
  60.   * @return 
  61.   */ 
  62.  public boolean findPath(byte[] map, int origin, int target) { 
  63.   if (canMoveTo(map, origin, target, 'l')) { 
  64.    return true; 
  65.   } 
  66.   if (canMoveTo(map, origin, target, 'r')) { 
  67.    return true; 
  68.   } 
  69.   if (canMoveTo(map, origin, target, 'u')) { 
  70.    return true; 
  71.   } 
  72.   if (canMoveTo(map, origin, target, 'd')) { 
  73.    return true; 
  74.   } 
  75.   stack.pop();// 如果四个方向都试过，全部不行，那么把当前步骤弹出 
  76.   return false; 
  77.  } 
  79.  /** 
  80.   * 是否可以向指定方向移动 
  81.   *  
  82.   * @param map 
  83.   * @param origin 
  84.   * @param target 
  85.   * @param direct 
  86.   * @return 
  87.   */ 
  88.  private boolean canMoveTo(byte[] map, int origin, int target, char direct) { 
  89.   int next = 0; 
  90.   switch (direct) { 
  91.   case 'l': 
  92.    next = origin - 1; 
  93.    break; 
  94.   case 'r': 
  95.    next = origin + 1; 
  96.    break; 
  97.   case 'u': 
  98.    next = origin - wid; 
  99.    break; 
  100.   case 'd': 
  101.    next = origin + wid; 
  102.    break; 
  103.   } 
  104.   if (map[next] == 0) {//如果目标位置可以进入 
  105.    if (next == target) { 
  106.     int[] step = new int[2]; 
  107.     step[0] = direct;// 移动方向 
  108.     step[1] = next;// 到达的新位置 
  109.     stack.addElement(step);     
  110.     return true; 
  111.    } 
  112.    if (!inStack(next)) { 
  113.     int[] step = new int[2]; 
  114.     step[0] = direct; 
  115.     step[1] = next; 
  116.     stack.addElement(step); 
  117.     if (findPath(map, next, target)) { 
  118.      return true; 
  119.     } 
  120.    } 
  121.   } 
  122.   return false; 
  123.  } 
  126.  /** 
  127.   * 检查这个位置是否在栈中已经存在了。为了防止在地图中转圈 
  128.   *  
  129.   * @param posi 
  130.   * @return 
  131.   */ 
  132.  private boolean inStack(int posi) { 
  133.   int[] temp; 
  134.   for (int i = stack.size() - 1; i >= 0; i--) { 
  135.    temp = (int[]) stack.elementAt(i); 
  136.    if (posi == temp[1]) { 
  137.     return true; 
  138.    } 
  139.   } 
  140.   return false; 
  141.  } 
  142. } 
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞