#include <bits/stdc++.h>
using namespace std;
using lint = long long int;


struct Graph {
    struct Edge { int from; int to; lint cost; };
    struct Node {
        Node() : par(-1), done(false), dist(INF) {}
        int index;
        int par;
        bool done;
        lint dist;
        vector<Edge> edge;
    };

    int n;
    vector<Node> nodes;
    vector<Edge> edges;
    const static lint INF = 1e18;

    Graph(int n) : n(n) {
        nodes.resize(n);
        for(int i=0; i<n; i++)  nodes[i].index = i;
    }

    void add_edge(int from, int to, lint cost) {
        nodes[from].edge.push_back(Edge{from, to, cost});
        edges.push_back(Edge{from, to, cost});
    }

    void dijkstra(int s) {
        using Cand = tuple<lint, int, int>; // (dist, index, from)
        priority_queue<Cand, vector<Cand>, greater<Cand>> que;
        que.emplace(0, s, -1);

        while(!que.empty()) {
            lint dist; int index, from;
            tie(dist, index, from) = que.top(); que.pop();
            if(dist >= nodes[index].dist)  continue;
            
            nodes[index].dist = dist;
            nodes[index].par = from;
            for(auto& e : nodes[index].edge) {
                que.emplace(dist + e.cost, e.to, e.from);
            }
        }
    }

    bool bellman_ford(int s) {
        bool negative_cycle;
        nodes[s].dist = 0;
        for(int step=1; step<=n; step++) {
            bool update = false;
            for(auto& e : edges) {
                if(nodes[e.from].dist == INF)  continue;

                lint next_cost = nodes[e.from].dist + e.cost;
                if(nodes[e.to].dist > next_cost) {
                    nodes[e.to].dist = next_cost;
                    nodes[e.to].par = e.from;
                    update = true;
                }
            }
            negative_cycle = (step == n && update);
        }
        return negative_cycle;
    }

    void bfs(int s) {
        queue<int> que;
        nodes[s].dist = 0;
        que.push(s);

        while(!que.empty()) {
            int index = que.front(); que.pop();
            for(auto& e : nodes[index].edge) {
                if(nodes[e.to].dist != INF)  continue;
                nodes[e.to].dist = nodes[index].dist + 1;
                nodes[e.to].par = index;
                que.push(e.to);
            }
        }
    }

    lint shortest_dist(int to) { return nodes[to].dist; }

    vector<int> shortest_path(int to) {
        vector<int> path;
        int index = to;
        while(index != -1) {
            path.push_back(index);
            index = nodes[index].par;
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

template<typename T> vector<T> tensor(int n, T v){ return vector<T>(n, v); }
template<typename... Ts> auto tensor(int n, Ts... ts) {
    return vector<decltype(tensor(ts...))>(n, tensor(ts...));
}

int main() {
    int h, w;
    cin >> h >> w;

    auto id = [&](int i, int j) {
        return (i-1)*w + (j-1);
    };

    auto grid = tensor(h+2, w+2, '$');
    for(int i=1; i<=h; i++)
    for(int j=1; j<=w; j++) {
        cin >> grid[i][j];
    }

    Graph g(h*w);
    for(int i=1; i<=h; i++)
    for(int j=1; j<=w; j++) {
        if(grid[i][j] == '#') {
            if(grid[i+1][j] != '$')  g.add_edge(id(i,j), id(i+1, j), 0);
            if(grid[i][j+1] != '$')  g.add_edge(id(i,j), id(i, j+1), 0);
        }
        if(grid[i][j] == '.') {
            if(grid[i+1][j] == '#')  g.add_edge(id(i,j), id(i+1, j), 1);
            else if(grid[i+1][j] == '.')  g.add_edge(id(i,j), id(i+1, j), 0);

            if(grid[i][j+1] == '#')  g.add_edge(id(i,j), id(i, j+1), 1);
            else if(grid[i][j+1] == '.')  g.add_edge(id(i,j), id(i, j+1), 0);
        }
    }

    int s = id(1, 1);
    int t = id(h, w);
    g.dijkstra(s);
    lint ans = g.shortest_dist(t);
    cout << (grid[1][1] == '#' ? ans+1 : ans) << endl;
}

Measured memory_bytes: 1660