Solution UVA: 124 - Following Orders

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss124 - Following Orders	Accepted	C++11	0.000	0.000	1611	42 secs ago

Tricky Lines :

Orderings are printed in lexicographical (alphabetical) order

Output for different constraint specifications is separated by a blank line.

Analysis :

backtracking

sort the variables

keep an 2d array ‘role’

role[{x,y}] = true, if x < y

so when role[{y,x}] == true, u must not go further

Solution :

#include<bits/stdc++.h>

using namespace std;

vector<char> a, v;

typedef pair<char, char> ii;

map<ii, bool> role;

unordered_map<char, bool> visited;

char x, y;

string s;

int test= 1;

void reset(){

    a.clear();

    role.clear();

    visited.clear();

}

bool pass_role(int y){

    for(auto x:v)

        if (role[{y,x}]) return false;

    return true;

}

void f(int u){

    if (u == a.size()){

        for(auto x:v) cout<<x;

        cout<<"\n";

    }

   

    for(int i=0; i<a.size(); i++)

        if (not visited[a[i]] and pass_role(a[i])){

           

            v.push_back(a[i]);

            visited[a[i]]= true;

           

            f(u+1);

           

            v.pop_back();

            visited[a[i]]= false;

        }  

}

int main(){

    while(getline(cin, s)){

   

        if (test++ != 1) cout<<"\n";    

       

        reset();

       

        istringstream is(s);    while(is >> x) a.push_back(x);

       

        sort(a.begin(), a.end());

       

        getline(cin, s);    istringstream iss(s);       while(iss >> x >> y) role[{x,y}]= true;

       

        f(0);  

    }

}

Ý tưởng từ https://tausiq.wordpress.com/2010/09/02/uva-124-following-orders/