#include<iostream>
#include<vector>
#include<utility>
using namespace std;

long long unseen = -1024;
long long none = -2187;
long long keyMax = 2401;
long long labelMax = 3125;

struct node
{long long v; long long w; struct node *next;};

typedef pair<long long, long long> itemType;

class PQ{
    public:
    itemType *a;
    int N;
    long long *address;
    PQ(long long max){
        a = new itemType[max + 1];
        a[0] = make_pair(keyMax, labelMax);
        N = 0;
        address = new long long[max + 1];
        for(long long i = 1; i <= max; i++) address[i] = none;
    }
    void upheap(long long k){
        itemType v;
        v = a[k];
        while(a[k/2].second < v.second){
            a[k] = a[k/2];
            address[a[k/2].first] = k;
            k = k/2;
        }
        a[k] = v;
        address[v.first] = k;
    }
    void downheap(long long k){
        long long j;
        itemType v;
        v = a[k];
        while(k <= N/2){
            j = k+k;
            if(j < N && a[j].second < a[j+1].second) j++;
            if(v.second >= a[j].second) break;
            a[k] = a[j];
            address[a[j].first] = k;
            k = j;
        }
        a[k] = v;
        address[v.first] = k;
    }
    void insert(itemType v){
        a[++N] = v;
        upheap(N);
    }
    itemType remove(){
        itemType v = a[1];
        address[v.first] = none;
        a[1] = a[N--];
        downheap(1);
        return v;
    }
    long long update(itemType v){
        long long updated = 1;
        if(address[v.first] == none){
            insert(v);
        }else if(a[address[v.first]].second < v.second){
            a[address[v.first]].second = v.second; //update go heap broken!!!!
            upheap(address[v.first]);
        }else{
            updated = 0;
        }
        return updated;
    }
    long long empty(){
        return !N;
    }
};

void visit(long long x, struct node *z, struct node **adj, long long *dad, long long *val, PQ prique){
    struct node *t;
    pair<long long, long long> p;
    if(prique.update(make_pair(x, 0))) dad[x] = x;
    while(!prique.empty()){
        p = prique.remove();
        val[p.first] = -val[p.first];
        if(val[p.first] == -unseen) val[p.first] = 0;
        
        for(t = adj[p.first]; t != z; t = t -> next)
        if(val[t -> v] < 0)
        if(prique.update(make_pair(t -> v, - t -> w - val[p.first]))){
            val[t -> v] = - t -> w - val[p.first];
            dad[t -> v] = p.first;
        }
        

    }
}

int main(){
    int H, W;
    cin >> H >> W;
    vector<long long> a_sub;
    vector<vector<long long> > a;
    long long i, j;
    for(j = 0; j <= W; j++){
        a_sub.push_back(0);
    }
    for(i = 0; i <= H; i++){
        a.push_back(a_sub);
    }
    string S;
    const char *s = NULL;
    for(i = 1; i <= H; i++){
        cin >> S;
        s = S.c_str();
        for(j = 1; j<= W; j++){
            if(s[j-1] == '#') a[i][j] = 1;
        }
    }

    long long V = H * W;
    struct node *adj[V + 1], *z;
    struct node *t;
    z = new node;
    z -> next = z;
    for(i = 1; i <= V; i++) adj[i] = z;

    for(i = 1; i <= H; i++){
        for(j = 1; j <= W-1; j++){
            t = new node;
            t -> v = (i-1)*W + j+1;
            if(a[i][j] == 1 && a[i][j+1] == 0) t -> w = 1;
            else t -> w = 0;
            t -> next = adj[(i-1)*W + j];
            adj[(i-1)*W + j] = t;
        }
    }
    for(j = 1; j <= W; j++){
        for(i = 1; i <= H-1; i++){
            t = new node;
            t -> v = i*W + j;
            if(a[i][j] == 1 && a[i+1][j] == 0) t -> w = 1;
            else t -> w = 0;
            t -> next = adj[(i-1)*W + j];
            adj[(i-1)*W + j] = t;
        }
    }

    long long val[V + 1];
    for(i = 1; i <= V; i++) val[i] = unseen; 
    long long dad[V + 1];
    PQ prique(V);
    visit(1, z, adj, dad, val, prique);

    if(a[H][W] == 1) val[V] = val[V] + 1;
    cout << val[V] << endl;
    system("pause");
    return 0;
}

Measured memory_bytes: 1656