Untitled

mail@pastecode.io avatar
unknown
csharp
a month ago
2.5 kB
6
Indexable
Never
public string DepthFirstSearch()
{
    this.stack.Clear();

    // Add starting location
    this.stack.Push(this.StartingPoint);

    // Get current location
    Point location;

    // Execute search
    while (this.stack.Size > 0)
    {
        location = this.stack.Top();

        // Exit found
        if (this.charMaze[location.Row][location.Column] == 'E')
        {
            exitFound = true;
            break;
        }

        // Path
        this.charMaze[location.Row][location.Column] = '.';

        if (this.charMaze[location.Row + 1][location.Column] == ' ' || this.charMaze[location.Row + 1][location.Column] == 'E')
        {
            // South
            this.stack.Push(new Point(location.Row + 1, location.Column));
        }
        else
        {
            if (this.charMaze[location.Row][location.Column + 1] == ' ' || this.charMaze[location.Row][location.Column + 1] == 'E')
            {
                // East
                this.stack.Push(new Point(location.Row, location.Column + 1));
            }
            else if (this.charMaze[location.Row][location.Column - 1] == ' ' || this.charMaze[location.Row][location.Column - 1] == 'E')
            {
                // West
                this.stack.Push(new Point(location.Row, location.Column - 1));
            }
            else if (this.charMaze[location.Row - 1][location.Column] == ' ' || this.charMaze[location.Row - 1][location.Column] == ' ')
            {
                // North
                this.stack.Push(new Point(location.Row - 1, location.Column));
            }
            else
            {
                // Visited
                this.charMaze[location.Row][location.Column] = 'V';

                // Backtrack
                this.stack.Pop();
            }
        }
    }

    this.searchComplete = true;

    // Reverse stack for output
    Stack<Point> pathStack = GetPathToFollow();
    string outputComment = "No exit found in maze!\n\n";
    string outputMaze = PrintMaze();
    string path = "";

    if (exitFound)
    {
        outputComment = string.Format("Path to follow from Start {0} to Exit {1} - {2} steps:\n", this.StartingPoint.ToString(), this.stack.Top(), this.stack.Size.ToString());
    }

    while (pathStack.Size > 0)
    {
        path += string.Format("{0}\n", pathStack.Pop());
    }

    return outputComment + path + outputMaze;
}
Leave a Comment