#!/bin/bash

# Function to recursively explore the labyrinth
explore() {
    local row=$1
    local col=$2

    # Mark the current cell as visited
    visited[$row,$col]=1

    # If we reached the center, exit
    if [ $row -eq $((rows / 2)) ] && [ $col -eq $((cols / 2)) ]; then
        echo "Exit found at row $row, column $col."
        exit 0
    fi

    # Check adjacent cells
    for ((i = 0; i < 4; i++)); do
        local next_row=$((row + delta_row[i]))
        local next_col=$((col + delta_col[i]))

        # Check if the next cell is valid
        if [ $next_row -ge 0 ] && [ $next_row -lt $rows ] && [ $next_col -ge 0 ] && [ $next_col -lt $cols ] && [ ${labyrinth[$next_row,$next_col]} -eq 1 ] && [ ${visited[$next_row,$next_col]} -eq 0 ]; then
            explore $next_row $next_col
        fi
    done
}

# Main function
main() {
    # Define the delta for movement (up, down, left, right)
    delta_row=(-1 1 0 0)
    delta_col=(0 0 -1 1)

    # Define the labyrinth association table (1 represents pathway)
    labyrinth=(
        (1 0 1 1 1)
        (1 1 1 0 1)
        (0 0 0 1 1)
        (1 1 1 1 0)
        (1 0 1 0 1)
    )

    rows=${#labyrinth[@]}
    cols=${#labyrinth[0]}

    # Declare an associative array to keep track of visited cells
    declare -A visited

    # Start exploring from the entrance (side of the table)
    for ((i = 0; i < $rows; i++)); local entrance_row=0
    local entrance_col=0
    while [ ${labyrinth[$entrance_row,$entrance_col]} -ne 1 ]; do
        if [ ${labyrinth[$i,0]} -eq 1 ]; then
            explore $i 0
        fi
((entrance_row++))
    done

    explore $entrance_row $entrance_col

    echo "No exit found."
    exit 1
}

main