[uvalive 7263] Today Is a Rainy Day（暴力，BFS，dp）

题目链接：https://vjudge.net/problem/UVALive-7263

题意：给两个字符串a,b，只包含1~6的数字，现在允许两种操作：1、修改某一位数字，2、修改整个串的某个数字，变成另外一个数字。问从b到a的最少操作。

首先2操作修改的比较多，假如都能打到最优解的情况下，尽可能多的2操作一定会比较优。

我们可以先不考虑字符串具体的变化，先考虑只有6位数的2操作的变化情况。

以012345为起点，预处理出需要多少种2操作才可以变成一个6为的目标串。

不必关心每一种数字有多少个，只需要关心2操作最少多少次。上述操作直接bfs就行了。

注意做法不对称：a到b和b到a结果不一样。

接下来枚举012345变成000000到555555的所有最小状态作为中间状态，由于1操作的存在，所以仅仅进行2操作是会多进行多余的操作的。所以实现记下：b到a的每一对数字的变化次数G，以及b中每一位数字出现的次数。

接下来枚举中间状态：b到中间状态是通过012345到中间状态的2操作映射获得的，那么通过这次映射以及操作，可以让b中的所有字符通过映射变成对应的字符，接下来只需要记录一共有多少位没有变到a就行了。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;

const int maxn = 66666;
const int inf = 0x7f7f7f7f;
unordered_map<string, int> id;
string di[maxn];
int G[11][11], vis[11];
int icnt, n;
int dp[maxn];
string a, b;
queue<int> q;
string itmp;

void dfs(int cnt) {
    if(cnt == 6) {
        id[itmp] = icnt; di[icnt++] = itmp;
        return;
    }
    for(int i = 0; i < 6; i++) {
        string bk = itmp;
        itmp += (i + '0');
        dfs(cnt+1);
        itmp = bk;
    }
}

void init() {
    string pre, cpy;
    itmp.clear(); pre.clear(); id.clear(); icnt = 0;
    dfs(0);
    for(int i = 0; i < icnt; i++) dp[i] = inf;
    for(int i = 0; i < 6; i++) pre += (i + '0');
    while(!q.empty()) q.pop();
    q.push(id[pre]); dp[id[pre]] = 0;
    while(!q.empty()) {
        int pid = q.front(); q.pop();
        pre = di[pid];
        for(int i = 0; i < 6; i++) {
            for(int j = 0; j < 6; j++) {
                cpy = pre;
                for(int k = 0; k < 6; k++) {
                    if(pre[k] == i + '0') cpy[k] = j + '0';
                }
                int cid = id[cpy];
                if(dp[cid] == inf) {
                    dp[cid] = dp[pid] + 1;
                    q.push(cid);
                }
            }
        }
    }
}

int main() {
    // freopen("in", "r", stdin);
    init();
    while(cin >> a >> b) {
        memset(G, 0, sizeof(G));
        memset(vis, 0, sizeof(vis));
        n = a.length();
        for(int i = 0; i < n; i++) {
            int u = b[i] - '1';
            int v = a[i] - '1';
            G[u][v]++; vis[u]++;
        }
        int ret = inf;
        for(int i = 0; i < icnt; i++) {
            string mid = di[i];
            int tmp = dp[i];
            for(int j = 0; j < 6; j++) {
                tmp += vis[j] - G[j][mid[j]-'0'];
            }
            ret = min(ret, tmp);
        }
        printf("%d
", ret);
    } 
    return 0;
}