1 条题解

  • 3
    @ 2023-12-17 14:23:15
    #include<bits/stdc++.h>
    using namespace std;
    struct node {
    	string _Str;
    	int _Tot;
    };
    unordered_map<string, bool> mp;
    string a, b;
    string A(string S, int x) {
    	string s = S;
    	if (s[x] == '9') s[x] = '1';
    	else s[x] ++;
    	return s;
    }
    string B(string S, int x) {
    	string s = S;
    	if (s[x] == '1') s[x] = '9';
    	else s[x] --;
    	return s;
    }
    void bfs() {
    	std::queue<node> q;
    	q.push((node) {
    		a, 0
    	});
    	while (!q.empty()) {
    		node now = q.front();
    		string s = now._Str;
    		int tot = now._Tot;
    		q.pop();
    		if (s == b) {
    			printf("%d", tot);
    			return;
    		}
    		tot ++;
    		for (int i = 0; i < 3; i ++) {
    			string cnt = s;
    			swap(cnt[i], cnt[i + 1]);
    			if (!mp[cnt])
    				q.push((node) {
    				cnt, tot
    			}), mp[cnt] = true;
    		}
    		for (int i = 0; i < 4; i ++) {
    			string cnt = A(s, i);
    			if (!mp[cnt])
    				q.push((node) {
    				cnt, tot
    			}), mp[cnt] = true;
    			cnt = B(s, i);
    			if (!mp[cnt])
    				q.push((node) {
    				cnt, tot
    			}), mp[cnt] = true;
    		}
    	}
    }
    int main() {
    	freopen("lock.in", "r", stdin);
    	freopen("lock.out", "w", stdout);
    	cin >> a >> b;
    	bfs();
    	return 0;
    }
    

    信息

    ID
    560
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    60
    已通过
    12
    上传者