首页 > 代码库 > topcoder SRM 618 DIV2 MovingRooksDiv2

topcoder SRM 618 DIV2 MovingRooksDiv2

2024-07-08 11:49:24   217人阅读

一开始Y1，Y2两个参数看不懂，再看一遍题目后才知道，vector<int>索引代表是行数，值代表的是列

此题数据量不大，直接深度搜索即可

注意这里深度搜索的访问标识不是以前的索引和元素，而是一个交换元素后的整个状态vector<int>，这样可以避免重复元素的搜索

    set<vector<int> > visit;    bool flag;    void dfs(vector<int>& src, vector<int>& dst){        if(src =http://www.mamicode.com/= dst ) flag =true;        if(flag) return;        if(visit.find(src)!=visit.end()) return;        visit.insert(src);        for(int i = 0 ; i < src.size(); ++ i){            for(int j = i+1; j <  src.size(); ++ j){                if(src[i] > src[j]){                    swap(src[i],src[j]);                    dfs(src,dst);                    swap(src[i],src[j]);                }            }        }    }    string move(vector <int> Y1, vector <int> Y2) {        visit.clear();        flag = false;        dfs(Y1, Y2);        if(flag) return "Possible";        else return "Impossible";    }

 


联系
我们