#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL maze(100) AS LONG
    LOCAL visited(100) AS LONG
    LOCAL path_stack(100) AS LONG
    LOCAL path_len AS LONG
    LOCAL maze_w AS LONG
    LOCAL maze_h AS LONG
    LOCAL start_pos AS LONG
    LOCAL end_pos AS LONG
    LOCAL cur_pos AS LONG
    LOCAL found_flag AS LONG
    LOCAL i AS LONG
    LOCAL nx AS LONG
    LOCAL ny AS LONG
    LOCAL temp_str AS STRING

    ' DFS maze solver with backtracking
    ' Grid: 0=open, 1=wall
    maze_w = 10
    maze_h = 10

    i = 0
    WHILE i < 100
        maze(i) = 0
        visited(i) = 0
        path_stack(i) = 0
        i = i + 1
    WEND

    ' Create maze walls
    maze(1 * maze_w + 1) = 1
    maze(1 * maze_w + 2) = 1
    maze(1 * maze_w + 3) = 1
    maze(2 * maze_w + 3) = 1
    maze(3 * maze_w + 1) = 1
    maze(3 * maze_w + 3) = 1
    maze(3 * maze_w + 5) = 1
    maze(3 * maze_w + 6) = 1
    maze(4 * maze_w + 5) = 1
    maze(5 * maze_w + 1) = 1
    maze(5 * maze_w + 2) = 1
    maze(5 * maze_w + 5) = 1
    maze(5 * maze_w + 7) = 1
    maze(6 * maze_w + 3) = 1
    maze(6 * maze_w + 5) = 1
    maze(6 * maze_w + 7) = 1
    maze(7 * maze_w + 1) = 1
    maze(7 * maze_w + 3) = 1
    maze(7 * maze_w + 7) = 1
    maze(8 * maze_w + 5) = 1
    maze(8 * maze_w + 8) = 1

    start_pos = 0
    end_pos = 9 * maze_w + 9
    found_flag = 0
    path_len = 0

    visited(start_pos) = 1
    path_stack(path_len) = start_pos
    path_len = path_len + 1
    cur_pos = start_pos

    WHILE path_len > 0 AND found_flag = 0
        cur_pos = path_stack(path_len - 1)

        IF cur_pos = end_pos THEN
            found_flag = 1
        ELSE
            nx = cur_pos MOD maze_w
            ny = cur_pos / maze_w
            i = 0
            WHILE i < 4 AND found_flag = 0
                IF i = 0 THEN
                    nx = (cur_pos MOD maze_w) + 1
                    ny = cur_pos / maze_w
                ELSEIF i = 1 THEN
                    nx = (cur_pos MOD maze_w) - 1
                    ny = cur_pos / maze_w
                ELSEIF i = 2 THEN
                    nx = cur_pos MOD maze_w
                    ny = cur_pos / maze_w + 1
                ELSEIF i = 3 THEN
                    nx = cur_pos MOD maze_w
                    ny = cur_pos / maze_w - 1
                END IF

                IF nx >= 0 AND nx < maze_w AND ny >= 0 AND ny < maze_h THEN
                    cur_pos = ny * maze_w + nx
                    IF maze(cur_pos) = 0 AND visited(cur_pos) = 0 THEN
                        visited(cur_pos) = 1
                        path_stack(path_len) = cur_pos
                        path_len = path_len + 1
                        IF cur_pos = end_pos THEN
                            found_flag = 1
                        END IF
                        i = 4
                    END IF
                END IF
                i = i + 1
            WEND

            IF found_flag = 0 THEN
                path_len = path_len - 1
            END IF
        END IF
    WEND

    PRINT "DFS Maze Solver (10x10 grid)"
    PRINT "==========================="
    PRINT ""
    PRINT "Maze layout (S=start, E=end, #=wall, .=path):"
    PRINT ""
    ny = 0
    WHILE ny < maze_h
        temp_str = ""
        nx = 0
        WHILE nx < maze_w
            cur_pos = ny * maze_w + nx
            IF cur_pos = start_pos THEN
                temp_str = temp_str + "S"
            ELSEIF cur_pos = end_pos THEN
                temp_str = temp_str + "E"
            ELSEIF maze(cur_pos) = 1 THEN
                temp_str = temp_str + "#"
            ELSE
                i = 0
                WHILE i < path_len
                    IF path_stack(i) = cur_pos THEN
                        temp_str = temp_str + "."
                    END IF
                    i = i + 1
                WEND
                IF LEN(temp_str) <= nx THEN
                    temp_str = temp_str + " "
                END IF
            END IF
            nx = nx + 1
        WEND
        PRINT temp_str
        ny = ny + 1
    WEND

    temp_str = STR$(path_len)
    PRINT ""
    PRINT "Path found: " + temp_str + " steps"
    PRINT "Path:"
    temp_str = ""
    i = 0
    WHILE i < path_len
        temp_str = temp_str + "(" + STR$(path_stack(i) MOD maze_w) + "," + STR$(path_stack(i) / maze_w) + ")"
        IF i < path_len - 1 THEN
            temp_str = temp_str + " -> "
        END IF
        i = i + 1
    WEND
    PRINT temp_str

    PRINT ""
    PRINT "DFS maze solver complete."

    FUNCTION = 0
END FUNCTION
