Recursive path finding issue

Question

I'm codding a path finding algorithm, and i need some help to figured out how to speed it a lot by avoid recursive goes on while an exception case is created.

I have 1 matrix ( spaces = walls; hash = blocs; 2 = actual position) The "2" need to gather all the "#", each time he walk onto a "#" it disappears.

I voluntary generated an impossible one to explain my issue.

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

As you can see, there is an unreachable island in the middle of the map.

I would like if you guys have any idea how to detect such of case. I can't figured out any way to.

heres my actual code :

Check some exceptions cases and return true or 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;
}

My Show function (MS-DOS windows)

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");
    }
}

My algorithm :

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;
    }
}

Answer 1

Maybe I'm crazy, but every time I see a problem involving disconnected contiguous regions I think disjoint sets. Disjoint sets are sets designed for very efficient merging, and merging is what you do a lot of if you're trying to find whether many regions of # are connected.

Put every location on your map into its own disjoint set. Any set containing a location will eventually contain all the locations you can move to from it. How? We walk around the map, and any time we can move from one place to another, we merge sets.

In what order should you take these steps? Flood-fill your entire map from somewhere -- make a flood-fill that goes, from each location, to any neighbor you didn't just come from. A flood-fill from point X to point Y should do nothing if X is in the same set as Y, but otherwise, should merge X and Y's sets if it's possible to move between them. If Y was never visited before, then recurse from Y.

This solution would run in about O(n inverse-ackermann(n)) for n locations in a map.