SRM 574 Div2 Medium TheNumberGameDiv2

問題

SRM 574 - TopCoder Wiki

数字Aを数字Bへ以下の操作で変換する. 変換にかかる最小手数を答えよ,もし変換が不可能であれば-1を答える問題

  • 最小桁の数字を削除しA/10とする
  • Aの数字を反転させる,12345ならば54321

解答

入力は9桁の数字.

  • 反転させた数字に反転させると元の数字になる
  • 最小桁の数字を削除すると入力のサイズが小さくなる
  • つまり操作を繰り返してもループが起こることがないので,全ての操作をシミュレーションしたとしても29程度.
  • 全探索で解く
using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

class TheNumberGameDiv2
{
  int rotate(int x){
    string s = toString(x);
    reverse(s.begin(), s.end());
    // cout << "rotate x=" << x << " return=" << s << endl << endl;
    return toInt(s);
  }
  int calc(int A, int B, bool canRotate) {
    if (A == B) return 0;
    if (A == 0) return -1;
    int res1 = calc(A/10, B, true);
    int res2 = -1;
    if (canRotate) {
      res2 = calc(rotate(A), B, false);
    }
    // cout << "(" << A << ", " << B << ", " << canRotate << ")="
    //      << "(res1:" << res1 << ", res2:" << res2 << ")"<< endl;
    if (res1 == -1 && res2 == -1) return -1;
    if (res1 == -1) return 1 + res2;
    if (res2 == -1) return 1 + res1;
    return 1 + min(res1, res2);
  }
public:
  int minimumMoves(int A, int B)
    {
      return calc(A, B, true);
    }
};