C++での覆面算パズル

方程式があるとすると、式は左側に単語で表され、結果は右側に表示されます。方程式が次の規則の下で解けるかどうかをチェックする必要があります-

• 各文字は1桁（0から9）としてデコードされます。

• 異なる文字のすべてのペアは、異なる数字にマップする必要があります。

• 各単語[i]と結果は、先行ゼロが存在しない数値としてデコードされます。

• 左側の数字の合計は右側の数字と等しくなります。

• 方程式が解けるかどうかを確認します。

したがって、入力がwords =["SEND"、 "MORE"]、result ="MONEY"の場合、文字を次のようにマップすると、出力はTrueになります。Map'S'-> 9、'E '-> 5、' N'-> 6、' D'-> 7、' M'-> 1、' O'-> 0、' R'-> 8、' Y'->' 2'、その後"SEND" + "MORE"="MONEY"は9567+1085=10652と同じです。

これを解決するには、次の手順に従います-

• サイズ：10の配列i2c、サイズ：26の配列c2i、および別の配列w

  を定義します。

• 関数solve（）を定義します。これには、idx、l、sum、

  が必要です。

• lがrのサイズと同じである場合、-

  • 合計が0と同じ場合はtrueを返します

• idxがwのサイズと同じである場合、-

  • c2i [r [l] --'A']のASCIIが-1に等しくない場合、-

    • c2i [r [l]--'A'のASCII]がsummod10と同じである場合、-

      • リターンsolve（0、l + 1、sum / 10）

  • それ以外の場合、i2c [sum mod 10]が-1と同じ場合、-

    • lがrのサイズと同じで、合計mod 10が0と同じ場合、-

      • falseを返す

    • c2i[r[l]-'A'のASCII]=sum mod 10

    • i2c [sum mod 10] =r[l]-'A'のASCII

    • temp：=resolve（0、l + 1、sum / 10）

    • c2i[r[l]-'A'のASCII]=-1

    • i2c [sum mod 10] =-1

    • 温度を返す

  • falseを返す

• l> =w [idx]のサイズの場合、-

  • リターンsolve（idx + 1、l、sum）

• c2i [w [idx、l]-'A']が-1に等しくない場合、-

  • lがw[idx]のサイズと同じでc2i[w[idx、l]-'A'のASCII]が0と同じ場合、-

    • falseを返す

  • 戻り値solve（idx + 1、l、sum + c2i [w [idx、l]-'A'のASCII]）

• 初期化i：=0の場合、i <10の場合、更新（iを1増やします）、実行-

  • i2c [i]が-1に等しくない場合、-

    • 次の部分を無視し、次の反復にスキップします

  • iが0と同じで、lがw [idx]のサイズと同じである場合、-

    • 次の部分を無視し、次の反復にスキップします

  • i2c [i]：=w [idx、l]-'A'のASCII

  • c2i [w [idx、l]-'A'のASCII]=i

  • temp：=resolve（idx + 1、l、sum + i）

  • i2c [i]：=-1

  • c2i [w [idx、l]-'A'のASCII]=--1

  • 温度がゼロ以外の場合、-

    • trueを返す

• falseを返す

• メインの方法から、次のようにします-

• i2cとc2iに-1を入力します

• 配列の結果を逆にする

• 初期化i：=0の場合、i <単語のサイズの場合、更新（iを1増やします）、do-

  • 単語のサイズ[i]>結果のサイズの場合、-

    • falseを返す

  • 配列の単語を逆にします[i]

• r：=結果、w：=単語

• リターンsolve（0、0、0）

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   char i2c[10];
   int c2i[26];
   vector<string> w;
   string r;
   bool solve(int idx, int l, int sum){
      if (l == r.size()) {
         return sum == 0;
      }
      if (idx == w.size()) {
         if (c2i[r[l] - 'A'] != -1) {
            if (c2i[r[l] - 'A'] == sum % 10) {
               return solve(0, l + 1, sum / 10);
            }
         }
         else if (i2c[sum % 10] == -1) {
            if (l == r.size() - 1 && sum % 10 == 0)
            return false;
            c2i[r[l] - 'A'] = sum % 10;
            i2c[sum % 10] = r[l] - 'A';
            bool temp = solve(0, l + 1, sum / 10);
            c2i[r[l] - 'A'] = -1;
            i2c[sum % 10] = -1;
            return temp;
         }
         return false;
      }
      if (l >= w[idx].size()) {
         return solve(idx + 1, l, sum);
      }
      if (c2i[w[idx][l] - 'A'] != -1) {
         if (l == w[idx].size() - 1 && c2i[w[idx][l] - 'A'] == 0){
            return false;
         }
         return solve(idx + 1, l, sum + c2i[w[idx][l] - 'A']);
      }
      for (int i = 0; i < 10; i++) {
         if (i2c[i] != -1)
         continue;
         if (i == 0 && l == w[idx].size() - 1)
         continue;
         i2c[i] = w[idx][l] - 'A';
         c2i[w[idx][l] - 'A'] = i;
         bool temp = solve(idx + 1, l, sum + i);
         i2c[i] = -1;
         c2i[w[idx][l] - 'A'] = -1;
         if (temp)
         return true;
      }
      return false;
   }
   bool isSolvable(vector<string>& words, string result){
      memset(i2c, -1, sizeof(i2c));
      memset(c2i, -1, sizeof(c2i));
      reverse(result.begin(), result.end());
      for (int i = 0; i < words.size(); i++) {
         if (words[i].size() > result.size())
         return false;
         reverse(words[i].begin(), words[i].end());
      }
      r = result;
      w = words;
      return solve(0, 0, 0);
   }
};
main(){
   Solution ob;
   vector<string> v = {"SEND","MORE"};
   cout << (ob.isSolvable(v, "MONEY"));
}

入力

{"SEND","MORE"}, "MONEY"

出力

1