当前位置: 首页 > 面试经验 >

keep笔试9.25华容道 c++

优质
小牛编辑
146浏览
2023-03-28

keep笔试9.25华容道 c++

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;
}

#Keep#
 类似资料: