c++ sol
\nclass Solution {\npublic:\n    int minimumDistance(string word) {\n        vector<vector<int>>dp(word.size(),vector<int>(word.size(),-1));\n        return dfs
```\nclass Solution {\npublic:\n    int minimumDistance(string word) {\n        vector<vector<int>>dp(word.size(),vector<int>(word.size(),-1));\n        return dfs(dp,word,-1,-1);\n    }\n    \n    int dfs(vector<vector<int>>&dp,string s,int l,int r){\n        int cur=max(l,r)+1;\n        if(cur>=s.size())return 0;\n        if(l!=-1&&r!=-1&&dp[l][r]!=-1)return dp[l][r];\n        char lc=\' \';\n        char rc=\' \';\n        if(l!=-1)lc=s[l];\n        if(r!=-1)rc=s[r];\n        int res=0;\n        int dis1=dis(lc,s[cur]);\n        int dis2=dis(rc,s[cur]);\n        res=min(dis1+dfs(dp,s,cur,r),dis2+dfs(dp,s,l,cur));\n        if(l!=-1&&r!=-1){\n            dp[l][r]=res;\n        }\n        return res;\n    }\n    \n    int dis(char a,char b)\n    {\n        if(a==\' \')return 0;\n        int n1=(int)(a-\'A\');\n        int r1=n1/6;\n        int c1=n1%6;\n        int n2=(int)(b-\'A\');\n        int r2=n2/6;\n        int c2=n2%6;\n        return abs(r1-r2)+abs(c1-c2);\n    }\n};\n```
[]