迷宫营救公主算法

新浪微博 QQ空间 腾讯微博

今天下班前在公司的技术题库中看到这道题目,思路很快就有了,递归遍历每一条可能的路径,然后找出最短的路径。回家把代码写出来了。发现算法效率实在是太低了,在矩阵较小的时候还好,当矩阵稍微大一点时根本算不过来,感觉复杂度像是O((N*M)^(N*M))这个数值太庞大了,也完全没有意义。公主等到花儿都谢啦。。

貌似这位同学的算法还不错,还没来得及研究,先做个链接:http://blog.csdn.net/joseph_1118/article/details/9390301

应付较小的矩阵下面的方法还是能蒙混过关的。先发到这里,后面再继续研究优化。题目和代码都在一起:

/**
* 公主被魔王抓走了,王子需要拯救出美丽的公主。他进入了魔王的城堡,魔王的城堡是一座很大的迷宫。
* 为了使问题简单化,我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙,王子不能通过。王子只
* 能移动到相邻(上下左右四个方向)的方格内,并且一秒只能移动一步。地图由’S’,’P’,’.’,’*’
* 四种符号构成,’.’表示王子可以通过,’*’表示墙,王子不能通过;’S’表示王子的位置;’P’表示公主
* 的位置;T表示公主存活的剩余时间,王子必须在T秒内到达公主的位置,才能救活公主。如下图所示:
*/

package com;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
* 公主被魔王抓走了,王子需要拯救出美丽的公主。他进入了魔王的城堡,魔王的城堡是一座很大的迷宫。
* 为了使问题简单化,我们假设这个迷宫是一个N*M的二维方格。迷宫里有一些墙,王子不能通过。王子只
* 能移动到相邻(上下左右四个方向)的方格内,并且一秒只能移动一步。地图由'S','P','.','*'
* 四种符号构成,'.'表示王子可以通过,'*'表示墙,王子不能通过;'S'表示王子的位置;'P'表示公主
* 的位置;T表示公主存活的剩余时间,王子必须在T秒内到达公主的位置,才能救活公主。如下图所示:
*/
public class SavePrincess
{
private int m;
private int n;
private char[][] visited;
private Map<Position, List<Position>> data = new HashMap<Position, List<Position>>();
private int t;
private Position s = null;
private Position p = null;

public static void main(String[] args)
{
char maze[][] = {
/* 0 1 2 3 4 5 6 7 8 9*/
/* 0 */{ '.', '*', '.', '.', '.', '*', '.', '.', '.', '.' },
/* 1 */{ '.', 'S', '*', '.', '.', '.', '.', '.', '.', '.' },
/* 2 */{ '.', '*', '*', '.', '.', '.', '.', '.', '.', '.' },
/* 3 */{ '.', '.', '*', '*', '*', '.', '.', '.', '.', '.' },
/* 4 */{ '.', '.', '.', '.', '.', '.', '.', '.', '.', '.' },
/* 5 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
/* 6 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
/* 7 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
/* 8 */{ '.', '.', '.', '.', '*', '.', '.', '.', '.', '.' },
/* 9 */{ '.', '.', 'P', '.', '*', '.', '.', '.', '.', '.' } };

// maze[][] = {
// /* 0 1 2 3 4 5 6 7 8 9 */
// /* 0 */{ '.', '.', '.', '*', '.', '.', '.', '.', '.', '.' },
// /* 1 */{ '.', 'S', '*', '.', '.', '.', '.', '.', '.', '.' },
// /* 2 */{ '.', '.', '*', '.', '.', '.', '.', '.', '.', '.' },
// /* 3 */{ '.', '.', '*', '*', '.', '*', '.', '.', '.', '.' },
// /* 4 */{ '.', '.', '.', '*', '.', '*', '.', '.', '.', '.' },
// /* 5 */{ '.', '.', '.', '*', '.', '.', '.', '.', '.', '.' },
// /* 6 */{ '.', '.', '*', '.', '.', '.', '.', '.', '.', '.' },
// /* 7 */{ '.', '.', '*', '.', '*', '.', '*', '.', '.', '.' },
// /* 8 */{ '.', '.', '.', '.', '*', '.', '*', '*', '*', '.' },
// /* 9 */{ '.', '.', '*', '.', '*', '.', '*', 'P', '.', '.' } };

new SavePrincess().saved(maze, 10, 8, 11);
}

/**
* @param vis
* M行N列迷宫
* @param m
* M
* @param n
* N
* @param t
* T
*
* @return boolean true表示营救成功,反之表示失败。
*/
public boolean saved(char[][] vis, int m, int n, int t)
{
this.m = m;
this.n = n;
this.visited = vis;
this.t = t;

for (int i = 0; i != m; i++)
{
for (int j = 0; j != n; j++)
{
System.out.print(visited[i][j]);
System.out.print(' ');
Position tmp = new Position(i, j);
switch (visited[i][j])
{
case '*':
break;
case 'S':
this.s = tmp;
break;
case '.':
prepareNode(i, j, tmp);
break;
case 'P':
this.p = tmp;
prepareNode(i, j, tmp);
default:
break;
}
}
System.out.println("");
}

if (s == null || p == null)
{
System.out.println("input visited error!");
return false;
}

Set<Position> excudedNode = new HashSet<Position>();
int l = findNearstWay(p, excudedNode);

if (l < 0)
{
System.out.println("failed saved the princess!");
return false;
}
else
{
System.out.println("Saved the princess in " + l + " seconds!");
return true;
}

}

private int findNearstWay(Position p2, Set<Position> excudedNode)
{
if (s.equals(p2))
{
return 0;
}


List<Position> lst = data.get(p2);
excudedNode.add(p2);

int minLen = -1;
if (lst == null)
{
return minLen;
}
for (Position o : lst)
{
if (excudedNode.contains(o))
{
continue;
}

int len = findNearstWay(o, excudedNode);

if ((len <= this.t && len != -1) && (minLen == -1 || (minLen != -1 && len < minLen)))
{
minLen = len;
}
}

excudedNode.remove(p2);
if (minLen != -1)
{
return minLen + 1;
}
else
{
return minLen;
}
}

private void prepareNode(int i, int j, Position tmp)
{
List<Position> lst1 = new LinkedList<Position>();
addOneNode(i + 1, j, lst1);
addOneNode(i, j + 1, lst1);
addOneNode(i - 1, j, lst1);
addOneNode(i, j - 1, lst1);
if (!lst1.isEmpty())
{
data.put(tmp, lst1);
}
}

private void addOneNode(int i, int j, List<Position> lst)
{
if (i >= m || i < 0 || j >= n || j < 0)
{
return;
}

switch (visited[i][j])
{
case '.':
case 'S':
lst.add(new Position(i, j));
break;
default:
break;
}
}
}

package com;

public class Position implements Comparable<Position>
{
private int i;
private int j;

public Position(int i, int j)
{
this.i = i;
this.j = j;
}

@Override
public int compareTo(Position o)
{
if (this.i == o.i && this.j == o.j)
{
return 0;
}
else if (this.i > o.i)
{
return 1;
}
else
{
if (this.i > o.j)
{
return 1;
}
else
{
return -1;
}
}
}

public boolean equals(Object o)
{
if (!(o instanceof Position))
{
return false;
}

if (this.compareTo((Position) o) == 0)
{
return true;
}

return false;
}

public int hashCode()
{
int result = 17;
result = 31 * result + i;
result = 31 * result + j;
return result;
}

public String toString()
{
return "(" + i + ", " + j + ")";
}
}

新浪微博 QQ空间 腾讯微博

| 1 分2 分3 分4 分5 分 (5.00- 9票)
Loading ... Loading ... | 这篇文章归档在:Java, 算法数据结构
| 标签: , . | 永久链接:链接 | 评论(2) |

2 条评论

  1. 评论于 十月 28, 2013 at 12:27:51 CST | 评论链接

    正解参考:链接

  2. nlqlove
    评论于 八月 10, 2013 at 22:09:51 CST | 评论链接

    你给的算法是深度优先的吧?

    可能是因为深度优先遍历时,步长变化太短了吧,如果把深度类比为循序查找。

    好像在你算法中没有看到记录状态,如果记录下已走过的路径,是不是就会节约很多次搜索时间呢?保证一个能走的格子只会走一次。

    之前看严蔚敏讲走迷宫时,他的迷宫数组有个是否走过的状态,采用深度遍历时,只要当该节点东南西北都走不通,回滚到上一步时,就会将该节点标记。

    你看下我的理解对不,是否可以提升下性能。

评论

邮箱地址不会被泄露, 标记为 * 的项目必填。

8 - 2 = *



You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <img alt="" src="" class=""> <pre class=""> <q cite=""> <s> <strike> <strong>

返回顶部