#include using namespace std; typedef long long int lli; #define pb push_back #define mp make_pair string keyboard[3] = {"QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"}; map > pos; string str; int d(int a, int b) { int dx = abs(pos[str[a]].first - pos[str[b]].first); int dy = abs(pos[str[a]].second - pos[str[b]].second); return dx + dy; } #define MAX 101 lli parent[MAX]; int path[MAX][MAX]; // stores which edges exist. map< pair >, bool> met; struct Node { pair n; int indx; int parent; lli dist; Node(pair n, int indx, lli dist) : n(n), dist(dist), indx(indx) {} bool operator < (Node const& other) const { return dist > other.dist; } }; lli dijkstra(lli s, int t) { priority_queue q; q.push(Node(mp(0, 1), 2, 0)); while (q.size()) { Node p = q.top(); q.pop(); if (met[mp(p.indx, p.n)] == false) { met[mp(p.indx, p.n)] = true; if (p.n.first == t || p.n.second == t) return p.dist; // go to next in string either with left or right finger. q.push(Node(mp(p.indx, p.n.second), p.indx + 1, p.dist + d(p.n.first, p.indx))); q.push(Node(mp(p.n.first, p.indx), p.indx + 1, p.dist + d(p.n.second, p.indx))); } } return 10000000; } int main() { for (int i = 0; i < 3; i++) { for (int k = 0; k < keyboard[i].size(); k++) { pos[keyboard[i][k]] = mp(i, k); } } cin >> str; str = "FJ" + str; cout << dijkstra(0, str.size() - 1) << "\n"; return 0; }