module deque_mod
    use,intrinsic :: iso_fortran_env
    implicit none
    type deque
        integer(int32),pointer:: v(:)
        integer(int32):: l,r
        integer(int32):: lmax, rmax
    end type
    private
    public:: deque
    public:: init_deque
    public:: append, appendleft
    public:: pop, popleft
    public:: right, left
    public:: remaining_elements
    public:: remain

contains
    subroutine init_deque(dq)
        ! 初期化
        type(deque):: dq
        dq%r=0; dq%rmax=1
        dq%l=1; dq%lmax=-1
        allocate(dq%v(dq%lmax:dq%rmax))
    end subroutine


    subroutine append(dq,num)
        ! 右端に挿入
        type(deque):: dq
        integer(int32):: num
        if (dq%r+1 > dq%rmax) call add_(dq)
        dq%r=dq%r+1
        dq%v(dq%r) = num
    end subroutine

    subroutine appendleft(dq,num)
        ! 左端に挿入
        type(deque):: dq
        integer(int32):: num
        if (dq%l-1 < dq%lmax) call add_(dq)
        dq%l=dq%l-1
        dq%v(dq%l) = num
    end subroutine

    subroutine add_(dq)
        ! arrayの延長
        type(deque):: dq
        integer(int32):: l
        integer(int32),pointer:: tmp(:)
        l = size(dq%v)
        allocate(tmp(l))
        tmp(:) = dq%v(:)
        deallocate(dq%v)
        allocate(dq%v(2*dq%lmax:2*dq%rmax))
        dq%v(dq%lmax:dq%rmax) = tmp(:)
        dq%lmax = 2*dq%lmax
        dq%rmax = 2*dq%rmax
    end subroutine


    function pop(dq) result(ret)
        ! 右端から取り出し
        type(deque):: dq
        integer(int32):: ret
        ret = dq%v(dq%r)
        dq%r=dq%r-1
    end function

    function popleft(dq) result(ret)
        ! 左端から取り出し
        type(deque):: dq
        integer(int32):: ret
        ret = dq%v(dq%l)
        dq%l=dq%l+1
    end function


    function right(dq) result(ret)
        ! 右端を確認
        type(deque):: dq
        integer(int32):: ret
        ret = dq%v(dq%r)
    end function

    function left(dq) result(ret)
        ! 左端を確認
        type(deque):: dq
        integer(int32):: ret
        ret = dq%v(dq%l)
    end function

    function remaining_elements(dq) result(ret)
        ! 残りの要素数
        type(deque):: dq
        integer(int32):: ret 
        ret = dq%r - dq%l + 1
    end function

    function remain(dq) result(ret)
        ! 要素が残っているかどうか
        type(deque):: dq
        logical:: ret
        ret = remaining_elements(dq) > 0
    end function
end module

program agc043a
    use deque_mod
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: h,w,i,j,a
    integer(int32), allocatable:: si(:,:)
    character(1),allocatable:: s(:,:)
    logical,allocatable:: booked(:,:)
    type(deque):: x_next, y_next

    read*, h,w
    allocate(s(w,h), si(w,h),booked(w,h))
    input_s : block
        character(w):: s_row
        do i=1,h
            read*, s_row
            do j=1,w
                s(j,i) = s_row(j:j)
            end do
        end do
    end block input_s

    call init_deque(x_next)
    call init_deque(y_next)

    call append(x_next,1)
    call append(y_next,1)

    si(:,:) = 1000000000
    si(1,1) = 0
    a = 0
    if (s(1,1) == '#') a=a+1
    if (s(w,h) =='#') a=a+1
    
    booked(:,:) = .false.
    booked(1,1) = .true.
    bfs : block
        integer(int32):: x,y
        do while(remain(x_next))
            x = popleft(x_next)
            y = popleft(y_next)
            if (x+1 <= w) then
                if (.not. booked(x+1,y)) then
                    booked(x+1,y) = .true.
                    call append(x_next,x+1)
                    call append(y_next,y)
                end if
                if (s(x,y) == s(x+1,y)) then
                    si(x+1,y) = min(si(x,y),si(x+1,y))
                else
                    si(x+1,y) = min(si(x,y)+1,si(x+1,y))
                end if
            end if

            if (y+1 <= h) then
                if (.not. booked(x,y+1)) then
                    booked(x,y+1) = .true.
                    call append(x_next,x)
                    call append(y_next,y+1)
                end if
                if (s(x,y) == s(x,y+1)) then
                    si(x,y+1) = min(si(x,y),si(x,y+1))
                else
                    si(x,y+1) = min(si(x,y)+1,si(x,y+1))
                end if
            end if
        end do
    end block bfs

    print'(i0)', (si(w,h)-a)/2 + a
end program agc043a

Measured memory_bytes: 768