module mod_linked_list
  implicit none
  integer, private, parameter :: intkind = 4

  type t_node
    private
    integer(intkind) :: item
    type(t_node), pointer :: prev => null()
    type(t_node), pointer :: next => null()
  end type t_node

  type t_linked_list
    integer :: size = 0
    type(t_node), private, pointer :: head => null()
    type(t_node), private, pointer :: tail => null()
  contains
    procedure :: add_first => add_first
    procedure :: add_last => add_last
    procedure :: poll_first => poll_first
    procedure :: poll_last => poll_last
    procedure :: peek_first => peek_first
    procedure :: peek_last => peek_last
    procedure :: clear => clear
    procedure :: get => get
    procedure :: remove => remove
    procedure :: replace => replace
    procedure :: first_index_of => first_index_of
    procedure :: last_index_of => last_index_of
    final :: finalize
  end type t_linked_list

contains

  subroutine finalize(this)
    type(t_linked_list), intent(inout) :: this
    call clear(this)
  end

  function new_node(item) result(res)
    integer(intkind), intent(in) :: item
    type(t_node), pointer :: res
    allocate(res)
    res%item = item
  end

  subroutine add_first(this, item)
    class(t_linked_list), intent(inout) :: this
    integer(intkind), intent(in) :: item
    type(t_node), pointer :: node
    node => new_node(item)
    if (associated(this%tail)) then
      node%next => this%head
      this%head%prev => node
    else
      this%tail => node
    end if
    this%head => node
    this%size = this%size + 1
  end

  subroutine add_last(this, item)
    class(t_linked_list), intent(inout) :: this
    integer(intkind), intent(in) :: item
    type(t_node), pointer :: node
    node => new_node(item)
    if (associated(this%head)) then
      node%prev => this%tail
      this%tail%next => node
    else
      this%head => node
    end if
    this%tail => node
    this%size = this%size + 1
  end

  integer(intkind) function poll_first(this) result(res)
    class(t_linked_list), intent(inout) :: this
    type(t_node), pointer :: node
    res = this%head%item
    node => this%head%next
    deallocate(this%head)
    this%head => node
    if (associated(node)) then
      node%prev => null()
    else
      this%tail => null()
    end if
    this%size = this%size - 1
  end

  integer(intkind) function poll_last(this) result(res)
    class(t_linked_list), intent(inout) :: this
    type(t_node), pointer :: node
    res = this%tail%item
    node => this%tail%prev
    deallocate(this%tail)
    this%tail => node
    if (associated(node)) then
      node%next => null()
    else
      this%head => null()
    end if
    this%size = this%size - 1
  end

  integer(intkind) function peek_first(this) result(res)
    class(t_linked_list), intent(in) :: this
    res = this%head%item
  end

  integer(intkind) function peek_last(this) result(res)
    class(t_linked_list), intent(in) :: this
    res = this%tail%item
  end

  subroutine clear(this)
    class(t_linked_list), intent(inout) :: this
    type(t_node), pointer :: node, next
    if (.not.associated(this%head)) return
    node => this%head
    do while (associated(node%next))
      next => node%next
      deallocate(node)
      node => next
    end do
    this%head => null()
    this%tail => null()
    this%size = 0
  end

  integer(intkind) function get(this, i) result(res)
    class(t_linked_list), intent(in) :: this
    integer, intent(in) :: i
    integer :: idx
    type(t_node), pointer :: node
    if (i <= (this%size + 1) / 2) then
      idx = 1
      node => this%head
      do while (idx < i)
        node => node%next
        idx = idx + 1
      end do
    else
      idx = this%size
      node => this%tail
      do while (idx > i)
        node => node%prev
        idx = idx - 1
      end do
    end if
    res = node%item
  end

  subroutine remove(this, i)
    class(t_linked_list), intent(inout) :: this
    integer, intent(in) :: i
    integer :: idx
    integer :: tmp
    type(t_node), pointer :: node
    if (i == 1) then
      tmp = poll_first(this)
      return
    end if
    if (i == this%size) then
      tmp = poll_last(this)
      return
    end if
    if (i <= (this%size + 1) / 2) then
      idx = 1
      node => this%head
      do while (idx < i)
        node => node%next
        idx = idx + 1
      end do
    else
      idx = this%size
      node => this%tail
      do while (idx > i)
        node => node%prev
        idx = idx - 1
      end do
    end if
    node%prev%next => node%next
    node%next%prev => node%prev
    deallocate(node)
    this%size = this%size - 1
  end

  subroutine replace(this, i, item)
    class(t_linked_list), intent(inout) :: this
    integer, intent(in) :: i
    integer(intkind), intent(in) :: item
    integer :: idx
    type(t_node), pointer :: node
    if (i <= (this%size + 1) / 2) then
      idx = 1
      node => this%head
      do while (idx < i)
        node => node%next
        idx = idx + 1
      end do
    else
      idx = this%size
      node => this%tail
      do while (idx > i)
        node => node%prev
        idx = idx - 1
      end do
    end if
    node%item = item
  end

  integer function first_index_of(this, item) result(res)
    class(t_linked_list), intent(in) :: this
    integer(intkind), intent(in) :: item
    type(t_node), pointer :: node
    res = 1
    node => this%head
    do while (associated(node))
      if (node%item == item) return
      node => node%next
      res = res + 1
    end do
    res = -1
  end

  integer function last_index_of(this, item) result(res)
    class(t_linked_list), intent(in) :: this
    integer(intkind), intent(in) :: item
    type(t_node), pointer :: node
    res = this%size
    node => this%tail
    do while (associated(node))
      if (node%item == item) return
      node => node%prev
      res = res - 1
    end do
    res = -1
  end

end module mod_linked_list
program wizard_in_maze
  use mod_linked_list
  implicit none
  integer, parameter :: inf = 1e9
  integer :: h, w, xs, ys, xg, yg, i, j, k, x, y
  integer :: g(-10:1010, -10:1010) = -1
  integer :: dx(4) = (/0, 1, 0, -1/)
  integer :: dy(4) = (/1, 0, -1, 0/)
  character(1000) :: s = ''
  type(t_linked_list) :: dequex, dequey
  read(*,*) h, w
  read(*,*) xs, ys
  read(*,*) xg, yg
  g(1:h, 1:w) = inf
  do i = 1, h
    read(*,*) s
    do j = 1, w
      if (s(j:j) == '#') g(i, j) = -1
    end do
  end do
  g(xs, ys) = 0
  call dequex%add_first(xs)
  call dequey%add_first(ys)
  do while (dequex%size > 0)
    x = dequex%poll_first()
    y = dequey%poll_first()
    do k = 1, 4
      i = x + dx(k)
      j = y + dy(k)
      if (g(i, j) > g(x, y)) then
        g(i, j) = g(x, y)
        call dequex%add_first(i)
        call dequey%add_first(j)
      end if
    end do
    do i = x - 2, x + 2
      do j = y - 2, y + 2
        if (g(i, j) > g(x, y) + 1) then
          g(i, j) = g(x, y) + 1
          call dequex%add_last(i)
          call dequey%add_last(j)
        end if
      end do
    end do
  end do
  write(*,'(i0)') merge(-1, g(xg, yg), g(xg, yg) == inf)
end program wizard_in_maze

Measured memory_bytes: 7408