#include using namespace std; #define int long long #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--) #define itn int #define all(x) (x).begin(),(x).end() #define F first #define S second const long long INF = 1LL << 60; const int MOD = 1000000007; template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } //https://www.creativ.xyz/dump-cpp-652/ #define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++) // vector template istream &operator>>(istream &is, vector &vec) { for (T &x : vec) is >> x; return is; } // pair template ostream &operator<<(ostream &os, pair &pair_var) { os << "(" << pair_var.first << ", " << pair_var.second << ")"; return os; } // vector template ostream &operator<<(ostream &os, const vector &vec) { os << "{"; for (int i = 0; i < vec.size(); i++) { os << vec[i] << (i + 1 == vec.size() ? "" : ", "); } os << "}"; return os; } // map template ostream &operator<<(ostream &os, map &map_var) { os << "{"; repi(itr, map_var) { os << *itr; itr++; if (itr != map_var.end()) os << ", "; itr--; } os << "}"; return os; } // set template ostream &operator<<(ostream &os, set &set_var) { os << "{"; repi(itr, set_var) { os << *itr; itr++; if (itr != set_var.end()) os << ", "; itr--; } os << "}"; return os; } #define DUMPOUT cerr void dump_func() { DUMPOUT << endl; } template void dump_func(Head &&head, Tail &&... tail) { DUMPOUT << head; if (sizeof...(Tail) > 0) { DUMPOUT << ", "; } dump_func(std::move(tail)...); } #ifdef DEBUG_ #define DEB #define dump(...) \ DUMPOUT << " " << string(#__VA_ARGS__) << ": " \ << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \ << endl \ << " ", \ dump_func(__VA_ARGS__) #else #define DEB if (false) #define dump(...) #endif signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int h,w; cin>>h>>w; vector > g(h,vector (w)); rep(i,h)rep(j,w) cin>>g[i][j]; vector > d(h,vector (w, INF)); priority_queue , vector >, greater >> pq; pq.push(make_tuple(0,0,0)); d[0][0] = 0; while(!pq.empty()){ auto tmp = pq.top(); pq.pop(); int cost = get <0>(tmp), y = get <1>(tmp), x = get <2>(tmp); if(y+1 < h){ if(g[y+1][x] == 'k'){ if(chmin(d[y+1][x],cost + y+2+x)){ pq.push(make_tuple(d[y+1][x], y+1, x)); } }else{ if(chmin(d[y+1][x], cost + 1)){ pq.push(make_tuple(d[y+1][x], y+1, x)); } } } if(x+1 < w){ if(g[y][x+1] == 'k'){ if(chmin(d[y][x+1],cost + y+2+x)){ pq.push(make_tuple(d[y][x+1], y, x+1)); } }else{ if(chmin(d[y][x+1],cost + 1)){ pq.push(make_tuple(d[y][x+1], y, x+1)); } } } } cout<