AcWing 184. 虫食算——DFS暴搜+剪枝
原题链接
简单
//DFS暴搜写法(4/10)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
using namespace std;
const int N = 26;
char a[N], b[N], c[N];
bool st[N];
unordered_map<char, int> m;
int n;
bool dfs(char x)
{
if(x == (char)('A' + n))
{
int t = 0;
bool flag = 1;
for(int i = n - 1; i >= 0; i --)
{
int s = m[a[i]] + m[b[i]] + t;
//cout << m[a[i]] << " " << m[b[i]] << endl;
if(s >= n)
{
t = 1;
s -= n;
}
else t = 0;
//cout << s << " " << endl;
if(s != m[c[i]])
{
flag = 0;
break;
}
}
//cout << endl;
if(flag == 0) return false;
return true;
}
for(int i = 0; i < n; i ++)
{
if(st[i] == 0)
{
st[i] = 1;
m[x] = i;
if(dfs((char)(x + 1))) return true;
st[i] = 0;
}
}
return false;
}
int main()
{
cin >> n;
scanf("%s%s%s", a, b, c);
//cout << a[0] << " " << b[0] << endl;
dfs('A');
for(char i = 'A'; i <= 'A' + n - 1; i ++)
cout << m[i] << " ";
cout << endl;
return 0;
}
--------------------------------------------------------------------------------
//DFS剪枝(10/10)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N = 30;
char c[3][N];
bool st[N];
int path[N];//path[x]存储的是x字母对应的数字
vector<int> q;
int n;
bool check()
{
int t = 0;
for(int i = n - 1; i >= 0; i --)
{
int a = path[c[0][i] - 'A'], b = path[c[1][i] - 'A'], z = path[c[2][i] - 'A'];
if(a != -1 && b != -1 && z != -1)
{
if(t != -1)
{
if(i == 0 && a + b + t >= n) return false;
if(i != 0 && (a + b + t) % n != z) return false;
t = (a + b + t) / n;
}
else
{
if(i == 0 && a + b >= n) return false;
if(i != 0 && (a + b + 0) % n != z && (a + b + 1) % n != z) return false;
}
}
else t = -1;
}
return true;
}
bool dfs(int idx)
{
if(idx == n) return true;
for(int i = 0; i < n; i ++)
{
if(st[i] == 0)
{
st[i] = 1;
path[q[idx]] = i;
if(check() && dfs(idx + 1)) return true;
st[i] = 0;
path[q[idx]] = -1;
}
}
return false;
}
int main()
{
cin >> n;
scanf("%s%s%s", c[0], c[1], c[2]);
for(int i = n - 1; i >= 0; i --)
{
int a = c[0][i] - 'A';
int b = c[1][i] - 'A';
int z = c[2][i] - 'A';
if(st[a] == 0)
{
st[a] = 1;
q.push_back(a);
}
if(st[b] == 0)
{
st[b] = 1;
q.push_back(b);
}
if(st[z] == 0)
{
st[z] = 1;
q.push_back(z);
}
}
memset(st, 0, sizeof st);
memset(path, -1, sizeof path);
dfs(0);
for(int i = 0; i < n; i ++)
printf("%d ", path[i]);
return 0;
}