int solve(vector<vector<int> >& edges, vector<int>& balls) { //处理邻接表 vector<vector<int> > my_edges(9); for (auto& edge : edges) { int x = edge[0]-1, y = edge[1]-1; my_edges[x].emplace_back(y); my_edges[y].emplace_back(x); } string target = "000000000"; string init; for (int i : balls) { init.push_back(('0'+i)); target[i-1] = ('0'+i); } init.push_back('0'); unordered_set<string> visited; queue<string> q; q.push(init); int deepth = 0; while (!q.empty()) { int n = q.size(); for (int i=0; i<n; i++) { string cur = q.front(); q.pop(); visited.insert(cur); if (cur == target) { return deepth; } int index = cur.find('0'); auto next = my_edges[index]; for (int j=0; j<next.size(); j++) { string t = cur; swap(t[index], t[next[j]]); if (visited.find(t) == visited.end()) { q.push(t); } } } deepth++; } return -1; } int main() { //5 // vector<vector<int> > edges = {{1,2},{1,3},{1,9},{2,9},{3,9}}; // vector<int> balls = {3,9,2,4,5,6,7,8}; //0 // vector<vector<int> > edges = {{1,2},{1,3},{1,9},{2,9},{3,9}}; // vector<int> balls = {1,2,3,4,5,6,7,8}; //-1 // vector<vector<int> > edges = {{8,5},{9,6},{4,5},{4,1},{2,5},{8,9},{2,1},{3,6},{8,7},{6,5},{7,4},{2,3}}; // vector<int> balls = {1,2,3,4,5,6,8,7}; //16 vector<vector<int> > edges = {{6,5},{5,4},{4,1},{4,7},{8,5},{2,1},{2,5},{6,9},{3,6},{9,8},{8,7},{3,2}}; vector<int> balls = {2,3,4,6,1,9,7,8}; int res = solve(edges, balls); cout<<res<<endl; return 0; }