0

我正在编写一个寻路算法，我需要一些帮助来弄清楚如何通过在创建异常情况时避免递归继续来加快它的速度。

我有 1 个矩阵（空格 = 墙壁；散列 = 块；2 = 实际位置）“2”需要收集所有“#”，每次他走到“#”时它都会消失。

我自愿产生了一个不可能的解释我的问题。

{  ,  ,  ,  ,  ,  ,  ,   };
{  , #, #, #, #, #, #,   };
{  , #,  ,  ,  ,  , #,   };
{  , #,  , #, #,  , #,   };
{  , #,  , #, #,  , #,   };
{  , #,  , #, #,  , #,   };
{  , #,  , #, #,  , #,   };
{  , #,  ,  ,  ,  , #,   };
{  , #, #, #, 2, #, #,   };
{  ,  ,  ,  ,  ,  ,  ,   };

如您所见，地图中间有一个无法到达的岛屿。

如果你们知道如何检测这种情况，我想知道。我想不出任何办法。

这是我的实际代码：

检查一些异常情况并返回 true 或 false ：

static bool BreakCaseFound() {
    int EndCases = 0;   // 3 blocs with 3 empty slots around
    bool BreakCases = false;    // 1 bloc with 4 empty slots around
    int temp = 0;
    for(int i = 1; i<17; i++) {
        for(int j = 1; j<17; j++) {
            if(matrice[j, i] == bloc) {
                if (matrice[j+1, i] == empty) {
                    temp++;
                }
                if (matrice[j-1, i] == empty) {
                    temp++;
                }
                if (matrice[j, i+1] == empty) {
                    temp++;
                }
                if (matrice[j, i-1] == empty) {
                    temp++;
                }
            }
            switch(temp) {
                case 3:
                    EndCases++;
                    temp = 0;
                    break;
                case 4:
                    temp = 0;
                    BreakCases = true;
                    break;
                default:
                    temp = 0;
                    break;
            }

            if(BreakCases || EndCases >= 3) {
                return true;
            }
        }
    }
    return false;
}

我的显示功能（MS-DOS 窗口）

static void show() {
    Console.Clear();
    for(int i =0; i<18; i++) {
        for(int j = 0; j<18; j++) {
            if(matrice[j,i] == empty) {
                Console.Write(" ");
            }
            else {
                if (matrice[j, i] == 2) { matrice[j, i] = bloc ; }
                if (matrice[j, i] == 3) { matrice[j, i] = 5 ; }
                Console.Write(matrice[j, i]);
            }
        }
        Console.Write("\n");
    }
}

我的算法：

static dynamic move(int actualPosCol, int actualPosLigne, List<int[]> path, List<int[]> RealPath)
{
    matrice[path[path.Count()-1][0], path[path.Count()-1][1]] = 5;
    show();
    if(nbBlocs > 0) {
        show();

        //Left move
        if( (matrice[path[path.Count() - 1][0]-1, path[path.Count() - 1][1]] == bloc)
        && (!BreakCaseFound()) ) { 
            nbBlocs--;
            matrice[actualPosCol, actualPosLigne] = empty;
            int[] posNext = new int[2] {actualPosCol-1, actualPosLigne};
            path.Add(posNext);
            move(actualPosCol-1, actualPosLigne, path, RealPath);
        }
        //Right move
        if( (matrice[path[path.Count() - 1][0]+1, path[path.Count() - 1][1]] == bloc)
        && (!BreakCaseFound()) ) { 
            nbBlocs--;
            matrice[actualPosCol, actualPosLigne] = empty;
            int[] posNext = new int[2] {actualPosCol+1, actualPosLigne};
            path.Add(posNext);
            move(actualPosCol+1, actualPosLigne, path, RealPath);

        }

        //Down move
        if ( (matrice[path[path.Count() - 1][0], path[path.Count() - 1][1]+1] == bloc)
        && (!BreakCaseFound()) ) { 
            nbBlocs--;
            matrice[actualPosCol, actualPosLigne] = empty;
            int[] posNext = new int[2] {actualPosCol, actualPosLigne+1};
            path.Add(posNext);
            move(actualPosCol, actualPosLigne+1, path, RealPath);
        }
        //Up move
        if ( (matrice[path[path.Count() - 1][0], path[path.Count() - 1][1]-1] == bloc)
        && (!BreakCaseFound()) ) { 
            nbBlocs--;
            matrice[actualPosCol, actualPosLigne] = empty;
            int[] posNext = new int[2] {actualPosCol, actualPosLigne-1};
            path.Add(posNext);
            move(actualPosCol, actualPosLigne-1, path, RealPath);
        }

        if(nbBlocs > 0) {
            //Can't move right, left, up or down
            matrice[path[path.Count() - 1][0], path[path.Count() - 1][1]] = 3;
            show();
            path.Remove(path.Last());   //remove last move from the List
            nbBlocs++;
        }

        return path;
    }
    else {  //No more blocs, path found.
        foreach(int[] way in path) {
            if(!RealPath.Contains(way)) {
                RealPath.Add(way);
            }
        }
        return path;
    }
}
4

1 回答 1

0

也许我疯了，但每次我看到涉及断开连接的连续区域的问题时，我都会认为是不相交的集合。不相交集是为非常有效的合并而设计的集，如果您试图找出# 的许多区域是否连接，则合并是您经常要做的事情。

将地图上的每个位置放入其自己的不相交集合中。任何包含位置的集合最终都将包含您可以从中移动到的所有位置。如何？我们在地图上四处走动，任何时候我们可以从一个地方移动到另一个地方，我们都会合并集合。

您应该按什么顺序执行这些步骤？从某个地方填满你的整个地图——做一个填满，从每个位置到你不只是来自的任何邻居。如果 X 与 Y 在同一个集合中，则从 X 点到 Y 点的洪水填充应该什么都不做，否则，如果可以在它们之间移动，则应该合并 X 和 Y 的集合。如果 Y 之前从未访问过，则从 Y 递归。

对于地图中的 n 个位置，该解决方案将运行大约 O(n inverse-ackermann(n))。

于 2013-04-13T02:35:12.320 回答