#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) typedef long long ll; typedef uint64_t ull; typedef pair P; typedef pair Pid; typedef pair Pdi; typedef pair Pl; typedef pair Pll; typedef pair> PP; typedef pair PPi; constexpr double PI = 3.1415926535897932; // acos(-1) constexpr double EPS = 1e-9; constexpr int INF = 1001001001; constexpr int mod = 1e+9 + 7; // constexpr int mod = 998244353; vector> dist(2005, vector(2005, 1e+15)); constexpr int dx[2] = {1, 0}; constexpr int dy[2] = {0, 1}; struct info{ int x, y, d; info(int x = 0, int y = 0, int d = 0) : x(x), y(y), d(d) {} }; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int h, w; cin >> h >> w; vector s(h); for(int i = 0; i < h; ++i) cin >> s[i]; queue que; dist[0][0] = 0; que.push(info(0, 0, 0)); while(!que.empty()){ info p = que.front(); que.pop(); int x = p.x, y = p.y, d = p.d; for(int i = 0; i < 2; ++i){ int nx = x + dx[i], ny = y + dy[i]; if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue; if(s[nx][ny] == '.'){ chmin(dist[nx][ny], dist[x][y] + 1); que.push(info(nx, ny, d + 1)); } else{ // s[nx][ny] == 'k' chmin(dist[nx][ny], dist[x][y] + 1 + (d + 1)); que.push(info(nx, ny, d + 1)); } } } cout << dist[h - 1][w - 1] << endl; }