#include #include #include using namespace std; map > chars; unsigned int dist(char a, char b){ return abs(chars[a].first -chars[b].first) + abs(chars[a].second -chars[b].second); } int main() { string s="QWERTYUIOP"; for(int i=0; i>s; int len = s.size(); unsigned int dp[110][30][30]; for(int k=0; k<=len; k++){ for(int l=0; l<26; l++){ for(int r=0; r<26; r++){ dp[k][l][r]=-1; } } } dp[0]['F'-'A']['J'-'A']=0; for(int k=1; k<=len; k++){ //dp[k][s[k-1]][j] for(int j=0; j<26; j++){ for(int l=0; l<26; l++){ if(dp[k-1][l][j]!=-1) dp[k][s[k-1]-'A'][j] = min(dp[k][s[k-1]-'A'][j], dp[k-1][l][j]+dist(l+'A', s[k-1])); } } for(int l=0; l<26; l++){ for(int r=0; r<26; r++){ if(dp[k-1][l][r]!=-1) dp[k][l][s[k-1]-'A'] = min(dp[k][l][s[k-1]-'A'], dp[k-1][l][r]+dist(r+'A', s[k-1])); } } } unsigned int sol=-1LL; for(int l=0; l<26; l++){ for(int r=0; r<26; r++){ sol = min(dp[len][l][r], sol); } } cout<