#!/usr/bin/env tclsh9.0
namespace import ::tcl::mathop::*

set rows 71; set cols 71
if {[llength $argv] == 1} {set rows [lindex $argv 0]; set cols $rows}

set inf [** 2 63]
set sr 1; set sc 1
set er $rows; set ec $cols
set bytes 1024

proc input {} {
    global rows cols grid sr sc er ec bytes

    # Put a border around the grid. This means all input coordinates will
    # have to be increased by 1.
    set border [list]
    for {set r 0} {$r <= $rows + 1} {incr r} {
        lappend border #
    }
    lappend grid $border

    for {set r 0} {$r < $rows} {incr r} {
        set row [list #]
        for {set c 0} {$c < $cols} {incr c} {
            lappend row .
        }
        lappend row #
        lappend grid $row
    }
    lappend grid $border

    set byte 0
    while {$byte < $bytes && [gets stdin line] >= 0} {
        if {$line eq ""} continue
        lassign [split $line ,] c r
        lset grid $r+1 $c+1 #
        incr byte
    }
}

proc show {} {
    global grid
    foreach row $grid {
        puts [join $row ""]
    }
}

# A* heuristic function. Takes row, column.
# Remember, we must NEVER overestimate the cost, but under is fine.
# Use Manhattan distance.
# Goal is in the bottom right corner, so we can skip abs().
proc h {r c} {
    global er ec
    expr {$er-$r + $ec-$c}
}

# A* search algorithm.  Our "nodes" are tuples of (row, col).
proc astar {} {
    global grid rows cols sr sc inf

    set openSet [dict create [list $sr $sc] 1]
    set cameFrom [dict create]
    set gScore [dict create [list $sr $sc] 0]
    set fScore [dict create [list $sr $sc] [h $sr $sc]]

    while {[dict size $openSet]} {
        set curr [cheapest $openSet $fScore]
        if {[atgoal $curr]} {
            return [score $cameFrom $curr]
        }
        set openSet [dict remove $openSet $curr]
        foreach node [neighbors $curr] {
            # All movement costs are 1.
            set g [+ [dict getdef $gScore $curr $inf] 1]
            if {$g < [dict getdef $gScore $node $inf]} {
                dict set cameFrom $node $curr
                dict set gScore $node $g
                dict set fScore $node [+ $g [h {*}$node]]
                dict set openSet $node 1
            }
        }
    }

    return -1
}

# In a real implementation, this would just pop the single cheapest node
# from the openSet priority queue.
proc cheapest {o f} {
    global inf
    if {[dict size $o] == 1} {return [lindex [dict keys $o] 0]}
    set first 1
    dict for {node _} $o {
        if {$first} {
            set c $node
            set first 0
            continue
        }
        if {! [dict exists $f $node]} continue
        if {[dict getdef $f $node $inf] < [dict getdef $f $c $inf]} {
            set c $node
        }
    }
    return $c
}

proc atgoal {curr} {
    global er ec
    expr {[lindex $curr 0] == $er && [lindex $curr 1] == $ec}
}

# Allowed moves are north, south, east, west, unless a wall is in the way.
proc neighbors {curr} {
    global grid

    lassign $curr r c
    set moves [list]
    foreach {dr dc} {0 -1 0 1 -1 0 1 0} {
        set r2 [+ $r $dr]
        set c2 [+ $c $dc]
        if {[lindex $grid $r2 $c2] eq "#"} continue
        lappend moves [list $r2 $c2]
    }
    return $moves
}

proc score {from curr} {
    global mcost tcost
    # puts $curr
    set total 0
    while {[dict exists $from $curr]} {
        set prev [dict get $from $curr]
        incr total
        set curr $prev
    }
    return $total
}

input
# show
# puts "rows=$rows cols=$cols sr=$sr sc=$sc er=$er ec=$ec"
puts [astar]