blokada

#include <bits/stdc++.h>

using namespace std;

#define MAXN 1001
const int INF = 0x3f3f3f3f;
int dx[8] = {1, 0, -1, 0, -1, -1, 1, 1};
int dy[8] = {0, -1, 0, 1, -1, 1, 1, -1};

char area[MAXN][MAXN];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  bool no_walls = true;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
  	for (int j = 0; j < m; j++) {
  		cin >> area[i][j];
  		if (area[i][j] == '#') no_walls = false;
  	}
  }
  if (no_walls) {
    cout << m << endl;
    return 0;
  }
  //cijene: bijelo polje - 1, crno polje - 0;
  //za svaku tocku u prvom stupcu pronadi najkraci put do bilokoje tocke u
  //zadnjem stupcu i odaberi najkraci od svih dobivenih
  int min_total_cost = INF;
  int price[n][m];
	memset(price, INF, sizeof(price));
  for (int i = 0; i < n; i++) {
  	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
  	int cost = area[i][0] == '.' ? 1 : 0;
  	price[i][0] = cost;
  	pq.push({cost, {i, 0}});
  	while (!pq.empty()) {
  	  pair <int, int> u;
  	  tie(cost, u) = pq.top();
  	  pq.pop();
  	  if (price[u.first][u.second] < cost) continue; //vec pronaden kraci put do ovdje
  	  price[u.first][u.second] = cost;
  	  if (cost > min_total_cost) break; //trenutni trosak je veci od minimalnog do sada - sigurno nije optimalno rj
  	  if (u.second == m - 1) { //pronaden najkraci put od trenutnog pocetka do tocke u zadnjem stupcu
  	  	if (cost < min_total_cost) {
  	  	  min_total_cost = cost;
  	  	}
  	  	break; //ne treba vise provjeravati za ovu pocetnu tocku
  	  }
  	  for (int i = 0; i < 8; i++) {
  		pair<int, int> v;
  		v.first = u.first + dx[i];
  		v.second = u.second + dy[i];
  		if (v.first == -1 || v.first == n || v.second == -1 || v.second == m) continue;
  		int v_cost = cost + (area[v.first][v.second] == '.' ? 1 : 0);
  		if (v_cost < price[v.first][v.second]) {
  		  price[v.first][v.second] = v_cost;
  		  pq.push({v_cost, v});
  		}
  	  }
  	}
  }
  cout << min_total_cost << endl;
  return 0;
}