題目鏈接:

https://vjudge.net/problem/UVA-12107

題意:

給出一個數(shù)字謎，要求修改盡量少的數(shù)，使修改后的數(shù)字謎只有唯一解。空格和數(shù)字可以隨意替換，但不能增刪，數(shù)字謎中所有涉及的數(shù)必須是沒有前導零的正數(shù)。輸入數(shù)字謎一定形如a*b=c，其中a、b、c分別最多有2、2、4位。

題解:

http://www.cnblogs.com/tyty-Somnuspoppy/p/6366725.html
1、因為輸出字典序最小，所以每一位數(shù)按“*0123456789”順序枚舉。

2、如果當前要修改的數(shù)與即將被修改的數(shù)相同，則cnt不加1。

3、檢查積的時候，為防超時，只枚舉兩個乘數(shù)，通過檢查積的位數(shù)和積的已確定數(shù)字來驗證。

4、遇到空格要跳過并檢查返回結果。

代碼:

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 // 16 const int maxn = 1e5+10; 17 18 string s,ss = "*0123456789"; 19 pair<int,int> mp[3]; 20 int maxd,num,len; 21 22 bool leadingzero(int x){ 23 for(int i=0; i<2; i++) 24 if(mp[i].first == x) return true; 25 return false; 26 } 27 28 int changetodigit(string str){ 29 int res = 0; 30 for(int i=0; i<(int)str.size(); i++) 31 res = res*10 + str[i]-'0'; 32 return res; 33 } 34 35 bool check(){ 36 int x = changetodigit(s.substr(mp[0].first,mp[0].second-mp[0].first+1)); 37 int y = changetodigit(s.substr(mp[1].first,mp[1].second-mp[1].first+1)); 38 char str[5]; 39 sprintf(str,"%d",x*y); 40 int len = strlen(str); 41 if(mp[2].second-mp[2].first+1 != len) return false; 42 for(int i=mp[2].first; i<=mp[2].second; i++){ 43 if(s[i] == '*') continue; 44 if(s[i] != str[i-mp[2].first]) return false; 45 } 46 return true; 47 } 48 49 void judge(int cur){ 50 if(num>1) return ; 51 if(cur == mp[1].second+1){ 52 if(check()) ++num; // 通過前兩個數(shù)字相乘 判斷有沒有可能等于第三個數(shù) 53 return ; 54 } 55 if(s[cur] != '*') judge(cur+1); 56 else{ 57 for(int i=1; i<11; i++){ // 枚舉前兩個數(shù)字 ’*‘ 的位置 的全部可能 58 if(i==1 && leadingzero(cur)) continue; 59 s[cur] = ss[i]; 60 judge(cur+1); 61 s[cur] = '*'; 62 } 63 } 64 } 65 66 67 bool dfs(int d,int cur){ 68 if(d >= maxd){ 69 string tmp = s; 70 num = 0; 71 judge(0); // 給出一種數(shù)字謎，判斷這種的是不是唯一解 72 if(num == 1) return true; 73 s = tmp; 74 return false; 75 } 76 77 if(cur == len) return false; 78 if(s[cur] == ' '){ 79 if(dfs(d,cur+1)) return true; 80 }else{ 81 char c = s[cur]; 82 for(int i=0; i<11; i++){ 83 if(i==1 && leadingzero(cur)) continue; 84 if(c == ss[i]) { 85 if(dfs(d,cur+1)) return true; 86 }else{ 87 s[cur] = ss[i]; 88 if(dfs(d+1,cur+1)) return true; 89 s[cur] = c; 90 } 91 } 92 } 93 return false; 94 95 } 96 97 int main(){ 98 int cas = 0; 99 while(getline(cin,s)){ 100 if(s[0] == '0') break; 101 len = s.size(); 102 int cnt=0,start=0; 103 for(int i=0; i<len; i++){ 104 if(s[i] == ' '){ 105 mp[cnt++] = make_pair(start,i-1); 106 start = i+1; 107 } 108 } 109 mp[cnt] = make_pair(start,len-1); 110 111 printf("Case %d: ",++cas); 112 for(maxd=0; ; maxd++){ // IDA*迭代加深搜索， 枚舉上限，最多修改的次數(shù) 113 if(dfs(0,0)){ 114 printf("%s\n",s.c_str()); 115 break; 116 } 117 } 118 } 119 120 return 0; 121 }

?

轉載于:https://www.cnblogs.com/yxg123123/p/6827597.html

總結

以上是生活随笔為你收集整理的紫书搜索 习题7-8 UVA - 12107 Digit Puzzle IDA*迭代加深搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。