###
DOI:
:1994.5(3):12-21

关于迷宫排序问题的研究
吴向军,陈国良
(中山大学计算机系,广州 510275;中国科学技术大学计算机科学系,合肥 230026)
ON SORTING OF M×N MAZE
Wu Xiangjun,Chen Guoliang
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2794   Download 2530
Received:February 12, 1991    Revised:November 21, 1991
> 中文摘要: 本文首先把迷宫排序问题推广为m×n迷宫(m>1,n>1)的排序问题,证明了m×n迷宫的任一初始状态能经过有限步移动转变成目标状态的充要条件,然后给出了一个m×n迷宫排序的算法,该算法的时间复杂度是O(mn(m+n)),空间复杂度是O(mn).最后还指出了它的时间复杂度的一个下界.这样,关于迷宫排序问题就基本上得到了圆满地解决.
Abstract:his paper considers the problem of sorting m×n maze (m>1, n>1 ) and proves an sufficient and necessary condition that anoriginal state can be changed into specified-target state in finite step for m×u maze, then presents a sorting algorithm for m×n maze, its time complexity is O(mn (m+n)), its space complexity is O (mn), finaly, this paper gives a lower bound and shows that the algorithm is optimal where m=n.
文章编号:     中图分类号:    文献标志码:
基金项目:
Foundation items:
Reference text:

吴向军,陈国良.关于迷宫排序问题的研究.软件学报,1994,5(3):12-21

Wu Xiangjun,Chen Guoliang.ON SORTING OF M×N MAZE.Journal of Software,1994,5(3):12-21