#include <stdio.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef vector<vector<int>> v2int;
typedef vector<ll> vll;
typedef vector<vector<ll>> v2ll;
typedef list<int> liint;
typedef pair<int, int> pint;
const int INF = int(2e9);
const ll LINF = ll(2e9) * ll(2e9);
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b) { a > b ? : a = b; }
template<class T, class C> void chmin(T& a, C b) { a < b ? : a = b; }

#include <algorithm>
#include <vector>
#include <unordered_map>
#include <queue>
#include <functional>
#include <climits>

class edge {
public:
    edge(int to, long long cost);
    int get_to() const;
    long long get_cost() const;
private:
    int to;
    long long cost;
};

edge::edge(int to, long long cost) : to(to), cost(cost) {}

int edge::get_to() const { return to; }

long long edge::get_cost() const { return cost; }

class dykstra {
private:
    //unordered_mapを使って隣接を構築
    //first:接続元、second:辺のコストと接続先
    std::unordered_map<int, std::vector<edge>> adj_list;
    int node_num;
    int start_point;
    std::vector<long long> costs;//距離を保持
    std::vector<bool> is_done;//確定ノードか否かを保持

public:
    dykstra(const int node_num, const std::unordered_map<int, std::vector<edge>>& adj_list);
    void calc_min_cost(int start);
    long long get_cost(int end) const;
};

dykstra::dykstra(const int node_num, const std::unordered_map<int, std::vector<edge>>& adj_list) :
    adj_list(adj_list),
    start_point(0),
    node_num(node_num),
    costs(node_num + 1, LLONG_MAX),
    is_done(node_num + 1, false)
{}

void dykstra::calc_min_cost(int start) {
    this->start_point = start;
    this->costs = std::vector<long long>(node_num + 1, LLONG_MAX);
    this->is_done = std::vector<bool>(node_num + 1, false);

    //優先度付きキューpairで頂点番号と最短距離を保持
    //firstの要素で比較されるので、firstが距離、secondを頂点番号とする
    std::priority_queue<std::pair<long long, int>,
        std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> p_queue;
    p_queue.push(std::make_pair(0, start));
    costs[start] = 0;

    while (1) {
        if (p_queue.empty() == true) break; //キューが空なら終了
        std::pair<long long, int> cost_node = p_queue.top();
        p_queue.pop();
        is_done[cost_node.second] = true; //キューから取り出した頂点を確定頂点とする
        for (auto& it : adj_list[cost_node.second]) {
            int adj_node = it.get_to();
            if (is_done[adj_node] == false) {
                long long adj_cost = it.get_cost() + cost_node.first;
                if (adj_cost < costs[adj_node]) {//計算された隣接頂点のコストが現在のコストより小さいなら
                    costs[adj_node] = adj_cost; //隣接頂点のコストを更新
                    p_queue.push(std::make_pair(adj_cost, adj_node));//キューに隣接頂点の情報を突っ込む
                }
            }
        }
    }
}

long long dykstra::get_cost(int end) const {
    return costs[end];
}


set<pair<int, int>> bfs(vector<vector<char>>& field, int H, int W, pair<int, int> s) {
    deque<pair<int, int>> que;
    que.push_back(s);
    set<pair<int, int>> visited;
    visited.insert(s);
    set<pair<int, int>> ans;
    vector<pair<int, int>> move = { make_pair(1, 0), make_pair(0, 1) };
    while (1) {
        if (que.size() <= 0) break;
        auto nd = que.front();
        que.pop_front();
        for (auto& m : move) {
            auto new_nd = nd;
            new_nd.first += m.first;
            new_nd.second += m.second;
            if (new_nd.first >= H) continue;
            if (new_nd.second >= W) continue;
            if (visited.count(new_nd) > 0) continue;
            if (field[new_nd.first][new_nd.second] == '.') continue;
            visited.insert(new_nd);
            que.push_back(new_nd);
            //if (new_nd.first + 1 >= H || new_nd.second + 1 >= W || field[new_nd.first + 1][new_nd.second] == '.' || field[new_nd.first][new_nd.second + 1] == '.') {
            ans.insert(new_nd);
            //}
            
        }
    }
    return ans;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int H, W;
    cin >> H >> W;
    vector<vector<char>> field(H, vector<char>(W));
    vector<vector<int>> nodes(H, vector<int>(W));
    vector<vector<int>> new_nodes(H, vector<int>(W, -1));
    int n = 0;
    rep(i, H) {
        rep(j, W) {
            cin >> field[i][j];
            nodes[i][j] = n;
            n++;
        }
    }

    //n = 0;
    //rep(i, H) {
    //    rep(j, W) {
    //        if (new_node[i][j] != -1) continue;
    //        if (field[i][j] == '.') {
    //            new_nodes[i][j] = n;
    //            n++;
    //            continue;
    //        }

    //    }
    //}


    unordered_map<int, std::vector<edge>> graph;
    rep(i, H) {
        rep(j, W) {
            int cost = 0;
            if (j + 1 < W) {
                if (field[i][j + 1] == '#') cost = 1;
                graph[nodes[i][j]].push_back(edge(nodes[i][j + 1], cost));
            }
            if (i + 1 < H) {
                cost = 0;
                if (field[i + 1][j] == '#') cost = 1;
                graph[nodes[i][j]].push_back(edge(nodes[i + 1][j], cost));
            }
        }
    }

    set<pair<int, int>> visited;
    rep(i, H) {
        rep(j, W) {
           
            if (visited.count(make_pair(i, j)) > 0) continue;
            if (field[i][j] == '.') continue;
            auto adj = bfs(field, H, W, make_pair(i, j));
            //if (i == 0 && j == 0 && adj.count(make_pair(H - 1, W - 1)) > 0) {
            //    cout << 1 << endl;
            //    return 0;
            //}
            visited.insert(make_pair(i, j));
            for (auto& a : adj) {
                visited.insert(a);
                graph[nodes[i][j]].push_back(edge(nodes[a.first][a.second], 0));
                //for (auto& b : adj) {
                //    if (a.first <= b.first && a.second <= b.second) {

                //    }
                //}
            }
        }
    }

    
    int add = 0;
    if (field[0][0] == '#') add++;
    dykstra dk(H * W, graph);
    dk.calc_min_cost(0);
    int ans = add + dk.get_cost(nodes[H - 1][W - 1]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3712