Monday, 15 February 2016

Map Coloring Problem Solution Using C++.

Solution:

#include<bits/stdc++.h>
using namespace std;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
vector<string>colors;
vector<string>states;
map<string,vector<string> >neighbors;
map<string,string>statesColors;

void initializeColor();
void initializeStates();
void initializeneighbors();
string get_color_of_state(string state);
bool check(string state,string color){
    for(int i = 0; i < neighbors[state].size(); i++){
        string neighborColor = statesColors[neighbors[state][i]];
        if(neighborColor == color)return false;
    }
    return true;
}

int main(){

    initializeColor();
    initializeStates();
    initializeneighbors();

    for(int i = 0; i < states.size(); i++){
        statesColors[states[i]] = get_color_of_state(states[i]);
    }
    for(int i = 0; i < statesColors.size(); i++)cout << states[i] << " : " << statesColors[states[i]] << endl;
    return 0;
}

string get_color_of_state(string state){
    for(int i = 0; i < colors.size(); i++){
        if(check(state,colors[i]))return colors[i];
    }
    return "None";
}

void initializeColor(){
    colors.push_back("Red");
    colors.push_back("Blue");
    colors.push_back("Green");
}

void initializeStates(){
    states.push_back("Dhaka");
    states.push_back("Khulna");
    states.push_back("Chittagong");
    states.push_back("Rajshahi");
    states.push_back("Barisal");
    states.push_back("Sylet");
    states.push_back("Ranghpur");
}
void initializeneighbors(){
    neighbors["Dhaka"].push_back("Khulna");
    neighbors["Dhaka"].push_back("Chittagong");
    neighbors["Dhaka"].push_back("Rajshahi");
    neighbors["Dhaka"].push_back("Barisal");
    neighbors["Dhaka"].push_back("Sylet");
    neighbors["Dhaka"].push_back("Ranghpur");

    neighbors["Khulna"].push_back("Dhaka");
    neighbors["Khulna"].push_back("Rajshahi");
    neighbors["Khulna"].push_back("Barisal");

    neighbors["Chittagong"].push_back("Dhaka");
    neighbors["Chittagong"].push_back("Sylet");

    neighbors["Sylet"].push_back("Chittagong");
    neighbors["Sylet"].push_back("Ranghpur");
    neighbors["Sylet"].push_back("Rajshahi");
    neighbors["Sylet"].push_back("Barisal");

    neighbors["Ranghpur"].push_back("Dhaka");
    neighbors["Ranghpur"].push_back("Sylet");

    neighbors["Rajshahi"].push_back("Dhaka");
    neighbors["Rajshahi"].push_back("Sylet");
    neighbors["Rajshahi"].push_back("Khulna");
    neighbors["Rajshahi"].push_back("Barisal");

    neighbors["Barisal"].push_back("Sylet");
    neighbors["Barisal"].push_back("Dhaka");
    neighbors["Barisal"].push_back("Rajshahi");
}

No comments:

Post a Comment