ABC224做题笔记

Atcoder Begineer Contest 224

D - 8 Puzzle on Graph

题目大意

给定一个 \(9\) 个顶点，\(m\) 条边的图，共有八个棋子分别在 \(p_1,p_2,p_3...p_8\)，问最终能否让第 \(i\) 个棋子放在 \(i\) 号节点上。

解题思路

考虑与八数码相同的做法。

将九个顶点对应的状态压缩成一个九位数，即每个定点上对应了哪个棋子。

令第 \(i\) 个定点上最开始的棋子编号是 \(r_i\)，没有棋子的顶点 \(u\) 的 \(r_u\) 为 \(9\)，就能够生成初始状态。

然后将这个九位数压入队列，跑 BFS 求解，再用一个 \(map\) 记录，最后判断能否达到 \(123456789\) 这个状态。

生成初始状态部分：

string str="999999999"; //一开始都没有摆棋子
for(int i=1,pos;i<=8;i++){
    cin>>pos;
    str[pos-1]=i+'0'; //读入第 i 个棋子的位置后替换相应位置
}

BFS 部分：

mp[str]=1;
q.push(str);

while(!q.empty()){
    str=q.front();
    q.pop();

    int u=1;
    for(int i=0;i<9;i++){
        if(str[i]=='9'){
            u+=i; //找到没有棋子的顶点的位置
            break;
        }
    }

    for(auto v:G[u]){
        string n_str=str;
        swap(n_str[u-1],n_str[v-1]);
        
        if(mp[n_str]){
            continue;
        }

        mp[n_str]=mp[str]+1;
        q.push(n_str);
    }
}

if(!mp["123456789"]) cout<<-1<<"\n"; //如果没有走过，就说明无法到达
else cout<<mp["123456789"]-1<<"\n";