import java.util.*

fun main(args: Array<String>) = AGC043A2.main()

object AGC043A2 {
    fun readInt() = readLine()!!.toInt()
    fun readInts() = readLine()!!.split(" ").map { it.toInt() }

    val field: GridField
    val colorGrid: Matrix<Boolean> // is white
    val flipsGrid: Matrix<Int>

    init {
        val (h, w) = readInts()
        val rows = (1..h).map { readLine()!!.map { (it == '.') } }
        colorGrid = Matrix(rows)
        field = GridField(w, h)
        flipsGrid = Matrix.of(w, h) { x, y -> h * w }
    }

    data class SearchState(val flips: Int, val friendColor: Boolean)

    fun main() {
        // println("grid:\n$colorGrid")

        val root = GridCell(field.width - 1, field.height - 1, field)
        val initialState = when (colorGrid[root]) {
            true -> SearchState(flips = 0, friendColor = true)
            false -> SearchState(flips = 1, friendColor = false)
        }
        val search = BreadthFirstSearch(root, initialState,
            shouldVisit = { from, to, state ->
                val ret = (from.x > to.x || from.y > to.y) &&
                        flipsGrid[to] > state.flips + 1
                ret
            },
            whenVisit = { from, to, state ->
                val newState =
                    if (colorGrid[to] != state.friendColor) SearchState(state.flips + 1, !state.friendColor)
                    else state
                flipsGrid[to] = newState.flips
                //println("$from -> $to")
                newState
            })
        search.traverse()
        // println("flips:\n$flipsGrid")

        val result = flipsGrid.get(0, 0)
        println((result + 1) / 2)
    }


    /*---------------------------------------------------------------------------------*/


    class Matrix<T>(rows: List<List<T>>) {
        companion object {
            fun <T> of(width: Int, height: Int, init: (x: Int, y: Int) -> T): Matrix<T> {
                return if (height == 0) Matrix(emptyList())
                else Matrix((0 until height).map { x ->
                    if (width == 0) emptyList()
                    else (0 until width).map { y -> init(x, y) }
                })
            }
        }

        private val rowsData: List<MutableList<T>>
        val width: Int
        val height: Int

        init {
            width = rows.firstOrNull()?.size ?: 0
            assert(rows.all { row -> row.size == width })
            rowsData = rows.map { it.toMutableList() }
            height = rowsData.size
        }

        val rows: List<List<T>> = rowsData
        val cols: List<List<T>>
            get() = if (width == 0) emptyList()
            else (0 until width).map { x ->
                if (height == 0) emptyList()
                else (0 until height).map { y -> get(x, y) }
            }

        fun get(x: Int, y: Int): T = rowsData[y][x]
        fun set(x: Int, y: Int, value: T) {
            rowsData[y][x] = value
        }

        operator fun get(c: GridCell): T = rowsData[c.y][c.x]
        operator fun set(c: GridCell, value: T) {
            rowsData[c.y][c.x] = value
        }


        fun <R> map(transform: (T) -> R): Matrix<R> = Matrix(
            rows = rows.map { it.map(transform) }
        )
    }

    interface Node {
        /**
         *  note:
         *      T.neighbors() must return Sequence of T.
         */
        fun neighbors(): Sequence<Node>
    }

    class GridField(val width: Int, val height: Int) {
        fun has(cell: GridCell): Boolean = (cell.x in 0 until width) && (cell.y in 0 until height)
    }

    data class GridCell(
        val x: Int, val y: Int,
        val gridField: GridField
    ) : Node {
        init {
            assert(gridField.has(this))
        }

        private fun createCellOf(x: Int, y: Int) = GridCell(x, y, gridField)
        override fun neighbors(): Sequence<GridCell> = sequenceOf(
            createCellOf(x - 1, y),
            createCellOf(x + 1, y),
            createCellOf(x, y - 1),
            createCellOf(x, y + 1)
        ).filter { gridField.has(it) }

        override fun toString(): String = "($x,$y)"
    }


    interface Search<T : Node> {
        fun traverseSequence(): Sequence<T>
        fun traverse(): Unit = traverseSequence().forEach { }
    }

    abstract class SearchBase<T : Node, S>(
        private val root: T,
        private val initialState: S,
        private val whenVisit: (from: T?, to: T, state: S) -> S = { f, t, s -> s },
        private val shouldVisit: (from: T, to: T, state: S) -> Boolean
    ) : Search<T> {
        abstract fun queue(p: Pair<T, S>)
        abstract fun pop(): Pair<T, S>?

        override fun traverseSequence(): Sequence<T> {
            val state = whenVisit(null, root, initialState)
            queue(root to state)
            return searchAll()
        }

        private fun searchAll(): Sequence<T> = generateSequence {
            pop()?.let { p ->
                val first = p.first
                val state = p.second
                first.neighbors().filter {
                    shouldVisit(first, it as T, state)
                }.forEach {
                    val newState = whenVisit(first, it as T, state)
                    queue(it as T to newState)
                }
                first
            }
        }
    }

    class DepthFirstSearch<T : Node, S>(
        root: T,
        initialState: S,
        whenVisit: (from: T?, to: T, state: S) -> S = { f, t, s -> s },
        shouldVisit: (from: T, to: T, state: S) -> Boolean
    ) : SearchBase<T, S>(root, initialState, whenVisit, shouldVisit) {
        private val stack = LinkedList<Pair<T, S>>()
        override fun queue(p: Pair<T, S>) {
            stack.addFirst(p)
        }

        override fun pop(): Pair<T, S>? {
            val first = stack.firstOrNull()
            if (first != null) stack.removeFirst()
            return first
        }
    }

    class BreadthFirstSearch<T : Node, S>(
        root: T,
        initialState: S,
        whenVisit: (from: T?, to: T, state: S) -> S = { f, t, s -> s },
        shouldVisit: (from: T, to: T, state: S) -> Boolean
    ) : SearchBase<T, S>(root, initialState, whenVisit, shouldVisit) {
        private val stack = LinkedList<Pair<T, S>>()
        override fun queue(p: Pair<T, S>) {
            stack.addLast(p)
        }

        override fun pop(): Pair<T, S>? {
            val first = stack.firstOrNull()
            if (first != null) stack.removeFirst()
            return first
        }
    }
}

Measured memory_bytes: 76324