#include #include #include #include #include #include #include #include #include using namespace std; //struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout< TP; char dx[4]={1,0,-1,0}; char dy[4]={0,1,0,-1}; int h,w; char a[2000][2000]; int ans[2000][2000]; priority_queue, greater<>> q; void bfs() { q.emplace(0, 0, 0, 0); int c,kc,x,y; while(!q.empty()) { tie(c, kc, x,y) = q.top(); q.pop(); if (x < 0 || x >= w) continue; if (y < 0 || y >= h) continue; if (ans[y][x] >= 0) continue; ans[y][x] = c; if (a[y][x] == 'k') { c = c*2 + 1 - kc; kc++; } else c++; for (int i=0; i<4; i++) { int xi = x + dx[i]; int yi = y + dy[i]; if (xi < 0 || xi >= w) continue; if (yi < 0 || yi >= h) continue; q.emplace(c, kc, xi, yi); } } } int main() { cin >> h >> w; for (int i=0; i> a[i][j]; ans[i][j] = -1; } } bfs(); cout << ans[h-1][w-1] << endl; }