【CSES】1670. Swap Game

題目連結

時間複雜度

$O (9!$ x
$1)$

解題想法

這題是一題比較進階的枚舉題，如果想要 AC 這一題的話，要同時懂一些比較進階的優化方法還有BFS的運作原理，不然這題想要過會有點困難

這一題用到了不少比較難的技巧，下面會一一敘述：

使用 unordered_map 實現
$O (1)$ 查詢字串是否重複

我當初在做的時候一直被查詢速度太慢卡 TLE，所以我就想說是不是可以找一個查找元素只需要

O (1)

的容器，來藉此優化頻繁查詢的速度
對此我就找到了 unordered_map 這個東西，他最大的優點就是可以實現

O (1)

查找元素，這也正是我需要的

簡化枚舉所有可能性的程式

在這邊我使用的技巧是開兩個陣列分別存我要 swap 的位置，這樣一來我就不需要另外寫 dir 出來處理了

壓縮狀態敘述

這個方法跟上面那個一樣，也是我在看了別人的程式碼之後才發現的，使用這個技巧的優點是我能夠簡單的使用一行程式碼完成原本需要好幾段程式才能夠完處理的事情

範例：比對當前狀態和目標狀態

如果這邊我是使用字串來做處理的話我可以直接將程式簡化成下面這樣，而不是像使用 vector<vector<int>> 或是 vector<int> 一樣，必須完整寫出每一格的比較程式，這樣可以大幅增加程式的整潔度


if( goal == str ){}

枚舉結合 BFS

這題會這麼做的原因是為了達到題目所需要的最短部數，因為只要好好利用 BFS 的特性就可以解決最段路徑或是步數的問題了

完整程式

























































/* Question : CSES 1670. Swap Game */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second

string goal = "123456789";
const int x[] = {0, 1, 2, 3, 4, 5, 1, 2, 4, 5, 7, 8};
const int y[] = {3, 4, 5, 6, 7, 8, 0, 1, 3, 4, 6, 7};
const int MAXN = 9e8 + 5;
const int Mod = 1e9 + 7;
int ans;
char ch;
unordered_map<string, bool> used;
string init;
queue<pair<string, int>> q;

signed main(){
    opt;
    for( int i = 0 ; i < 9 ; i++ ){
        cin >> ch;
        init.push_back(ch);
    }

    q.push({init, 0});
    used[init] = true;

    while( !q.empty() ){
        string str = q.front().f;
        int level = q.front().s;
        q.pop();

        if( goal == str ){
            ans = level;
            break;
        }

        for( int i = 0 ; i < 12 ; i++ ){
            swap(str[x[i]], str[y[i]]);

            if( used.find(str) == used.end() ){
                used[str] = true;
                q.push({str, level+1});
            }

            swap(str[x[i]], str[y[i]]);
        }
    }

    cout << ans << "\n";
}