module mod_leftist_heap
  implicit none
  type t_key
    integer :: distance, count, x, y, direction
  end type
  type t_node
    type(t_node), private, pointer :: left => null(), right => null()
    integer :: rank = 1
    type(t_key), pointer :: key
  end type
  type leftist_heap
    integer :: size = 0
    type(t_node), private, pointer :: root => null()
  contains
    procedure :: offer => offer
    procedure :: poll => poll
    procedure :: meld => meld
  end type
contains
  logical function less(a, b) result(res)
    type(t_node), pointer, intent(in) :: a, b
    res = a%key%distance < b%key%distance
  end
  subroutine swap(a, b)
    type(t_node), pointer, intent(inout) :: a, b
    type(t_node), pointer :: c
    c => a
    a => b
    b => c
  end
  function newk0(distance, count, x, y, direction) result(res)
    integer, intent(in) :: distance, count, x, y, direction
    type(t_key), pointer :: res
    res => null()
    allocate(res)
    res%distance = distance
    res%count = count
    res%x = x
    res%y = y
    res%direction = direction
  end
  function newn0(key) result(res)
    type(t_key), pointer, intent(in) :: key
    type(t_node), pointer :: res
    res => null()
    allocate(res)
    res%key => key
  end
  recursive function meld_node(a, b) result(res)
    type(t_node), pointer, intent(in) :: a, b
    type(t_node), pointer :: res
    logical :: f
    if (.not.associated(a)) then
      res => b; return
    end if
    if (.not.associated(b)) then
      res => a; return
    end if
    if (less(a, b)) then
      res => a
      res%right => meld_node(res%right, b)
    else
      res => b
      res%right => meld_node(res%right, a)
    end if
    f = .not.associated(res%left)
    if (.not.f) f = res%left%rank < res%right%rank
    if (f) call swap(res%left, res%right)
    res%rank = merge(res%right%rank, 0, associated(res%right)) + 1
  end
  function poll(this) result(res)
    class(leftist_heap), intent(inout) :: this
    type(t_node), pointer :: left, right
    type(t_key), pointer :: res
    res => this%root%key
    left => this%root%left
    right => this%root%right
    deallocate(this%root)
    this%root => meld_node(left, right)
    this%size = this%size - 1
  end
  subroutine offer(this, distance, count, x, y, direction)
    class(leftist_heap), intent(inout) :: this
    integer, intent(in) :: distance, count, x, y, direction
    this%root => meld_node(this%root, newn0(newk0(distance, count, x, y, direction)))
    this%size = this%size + 1
  end
  type(leftist_heap) function meld(this, other) result(res)
    class(leftist_heap), intent(in) :: this
    type(leftist_heap), intent(in) :: other
    res%root => meld_node(this%root, other%root)
    res%size = this%size + other%size
  end
end module mod_leftist_heap
program pond_skater
  use mod_leftist_heap
  implicit none
  integer, parameter :: infty = lshift(1, 30)
  integer :: h, w, k, x(2), y(2), i, j
  integer :: dx(4) = (/0, 1, 0, -1/), dy(4) = (/1, 0, -1, 0/)
  integer :: dist, cnt, p, q, idx, u, v, cost, next
  integer, allocatable :: a(:, :, :)
  character(1000000) :: s
  type(leftist_heap) :: pq
  type(t_key), pointer :: key
  read(*,*) h, w, k
  read(*,*) x(1), y(1), x(2), y(2)
  allocate(a(0:h + 1, 0:w + 1, 4))
  a = -1
  do i = 1, h
    read(*,*) s
    do j = 1, w
      if (s(j:j) == '.') a(i, j, :) = infty
    end do
  end do
  a(x(1), y(1), :) = 0
  do i = 1, 4
    call pq%offer(0, k - 1, x(1), y(1), i)
  end do
  do while (pq%size > 0)
    key => pq%poll()
    dist = key%distance
    cnt = key%count
    p = key%x
    q = key%y
    idx = key%direction
    if (a(p, q, idx) < dist) cycle
    do i = 1, 4
      u = p + dx(i)
      v = q + dy(i)
      if (i == idx) then
        cost = 0
        next = cnt + 1
        if (next >= k) then
          cost = 1
          next = 0
        end if
        if (a(u, v, i) > dist + cost) then
          a(u, v, i) = dist + cost
          call pq%offer(a(u, v, i), next, u, v, i)
        end if
      else
        if (a(u, v, i) > dist + 1) then
          a(u, v, i) = dist + 1
          call pq%offer(a(u, v, i), 0, u, v, i)
        end if
      end if
    end do
  end do
  dist = minval(a(x(2), y(2), :))
  write(*,'(i0)') merge(-1, dist, dist == infty)
end program pond_skater

Measured memory_bytes: 110196