| 摘要: |
| 本文首先把迷宫排序问题推广为ｍ×ｎ迷宫（ｍ＞１，ｎ＞１）的排序问题，证明了ｍ×ｎ迷宫的任一初始状态能经过有限步移动转变成目标状态的充要条件，然后给出了一个ｍ×ｎ迷宫排序的算法，该算法的时间复杂度是Ｏ（ｍｎ（ｍ＋ｎ）），空间复杂度是Ｏ（ｍｎ）．最后还指出了它的时间复杂度的一个下界．这样，关于迷宫排序问题就基本上得到了圆满地解决． |
| 关键词: m×n迷宫（m＞1，n＞1），迷宫状态序列，数字i的逆序数1（i），迷宫状态的逆序数r（m，n），迷宫状态的特征值f（m，n）． |
| DOI： |
| 分类号: |
| 基金项目: |
|
| ON SORTING OF M×N MAZE |
|
Wu Xiangjun,Chen Guoliang
|
| 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. |
| Key words: m×n maze (m>1,n>1) state sequence reverse order number l(i) of i reverse order number r (m,n) of state eigenvalue f(m, n) of state. |
