CareerCup Cryptarithmetic Puzzle DFS(二)
epth]] == -1 || res[s1[s1len-depth]] == x)&&(!exist[y] && res[s2[s2len-depth]] == -1 || res[s2[s2len-depth]] == y)&&(!exist[num%10] && res[s3[s3len-depth]] == -1 || res[s3[s3len-depth]] == num%10); } void setFlg(string& s1, string& s2, string& s3, int depth, int x, int y, int z, bool flgX, bool flgY, bool flgZ) { int s1len = s1.length(), s2len = s2.length(), s3len = s3.length(); res[s1[s1len-depth]] = x, res[s2[s2len-depth]] = y,res[s3[s3len-depth]] = z; exist[x] = flgX, exist[y] = flgY, exist[z] = flgZ; } bool dfs(string& s1, string& s2, string& s3, int carry, int depth) { int s1len = s1.length(), s2len = s2.length(), s3len = s3.length(),i,j,x = 0,y = 0, saveX, saveY, saveZ; bool saveFlgX, saveFlgY, saveFlgZ; for (i = 0; i <= 9; ++i) for (j = 0; j <=9; ++j) { int num = i + j + carry; if (isValid(s1, s2, s3, num, depth, i, j)) { saveX = res[s1[s1len-depth]], saveY = res[s2[s2len-depth]], saveZ = res[s3[s3len-depth]], saveFlgX = exist[i], saveFlgY = exist[j], saveFlgZ = exist[num%10]; setFlg(s1, s2, s3, depth, i, j, num%10, true, true, true); if (depth == s2len) { if (s3len - s2len == 0 && num / 10 == 0) return true; else if (s3len > s2len && (res[s3[s3len-depth-1]] == -1 && !exist[num/10] || res[s3[s3len-depth-1]] == num/10)) { res[s3[s3len-depth-1]] = num/10; exist[num/10] = true; return true; } } else { if (dfs(s1, s2, s3, num / 10, depth + 1)) return true; } res[s1[s1len-depth]] = saveX, res[s2[s2len-depth]] = saveY, res[s3[s3len-depth]] = saveZ, exist[i] = saveFlgX, exist[j] = saveFlgY,exist[num%10] = saveFlgZ; } } return false; } bool check(string& s1, string& s2, string& s3) { int s1len = s1.length(), s2len = s2.length(), s3len = s3.length(),i,j; string s = s1 + s2 + s3; for (i = 0; i < s.length(); ++i) if (res.find(s[i]) == res.end()) { res.insert(make_pair(s[i],-1)); } memset(exist, false, sizeof(exist)); if (res.size() >10 ||s1len > s3len) return false; int s1s2len = max(s1len, s2len); for (i = 0; i < (s3len - s1s2len - 1); ++i) { if (res[s3[i]] == -1 && !exist[0]) { res[s3[i]] = 0; exist[0] = true; } else if (exist[0]) return false; } return s1len < s2len dfs(s2, s1, s3, 0, 1):dfs(s1, s2, s3, 0, 1); } }; int main() { Solution s; string a = "SEND", b = "MORE", c = "MONEY"; bool res = s.check(a,b,c); return 0; }