Solution UVA: 291 - The House Of Santa Claus

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss291 - The House Of Santa Claus	Accepted	C++11	0.000	0.000	2555	3 mins ago

Suggest:

- This problem can easily solve with Backtracking Algorithms

#include<bits/stdc++.h>

using namespace std;

bool a[6][6];

set<string> res;

bool ok(){

    for(int i=1; i<=5; i++)

    for(int j=1; j<=5; j++)

        if (a[i][j]) return false;

    return true;

}

void f(int u, string s){

    if (s.size() == 9){

        if (ok) res.insert(s);

        return;

    }

   

    for(int v=1; v<=5; v++)

        if (a[u][v]){

           

            a[u][v]= false, a[v][u]= false;

            f(v, s + to_string(v));

            a[u][v]= true,  a[v][u]= true;

        }

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    a[1][2]= true, a[1][3]= true, a[1][5]= true;

    a[2][1]= true, a[2][3]= true, a[2][5]= true;

    a[3][1]= true, a[3][2]= true, a[3][4]= true, a[3][5]= true;

    a[4][3]= true, a[4][5]= true;

    a[5][1]= true, a[5][2]= true, a[5][3]= true, a[5][4]= true;

    f(1, "1");

    for(auto x:res) cout<<x<<"\n";

}