Monday, 27 August 2018

Correct Graph coloring
#include<iostream>

using namespace std;
int c,n;
int arr[5][5];
int color_vertex[5];

void printSolution(int color_vertex[]){
  for(int i=0;i<n;i++){
    std::cout<<color_vertex[i]<<" ";
  }
  std::cout<<std::endl;
}

bool isSafe(int v,int col,int color_vertex[]){
 std::cout<<"color is :"<<col << " vertes is : "<<v<<std::endl;
  for(int i=0;i<n;i++){
    //std::cout<<"neighbours are : "<<i << " color is "<<col<<std::endl;
    if(arr[v][i]==1 && col==color_vertex[i]){return false;}

  }
 return true;
}


bool graphcoloringutil(int v,int color_vertex[]){
if(v==n){return true;}

//consider this vertex v and try diff. colors
for(int col=1;col<=c;col++){
    if(isSafe(v,col,color_vertex)==true){
        color_vertex[v]=col;

        if(graphcoloringutil(v+1,color_vertex)==true){return true;}

        //if not the right color :( remove it :
        color_vertex[v]=0;
    }
}


return false;
}


bool graph_coloring(int color_vertex[]){

for(int i=0;i<n;i++){color_vertex[i]=0;}

if(graphcoloringutil(0,color_vertex)==false){
    std::cout<<"no sol" <<std::endl;
    return false;
}

printSolution(color_vertex);
return true;
}

int main(){
int t;
std::cin>>t;
for(int tc=0;tc<t;tc++){
 std:cin>>n;
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        std::cin>>arr[i][j];
    }
}
  std::cin>>c;
  graph_coloring(color_vertex);
}

return 0;}



Correct backtracking of optimal path in maze\
#include<iostream>

using namespace std;
int arr[10][10];
int visited[10][10];
int min_cost;
int n;

bool isSafe(int x,int y){
 if(x>=0 && y>=0 && x<n && y<n && arr[x][y]!=0 ){return true;}
 else{return false;}
}

bool AllVisited(){
  for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(visited[i][j]!=1){return false;}
        }
    }
    return true;
}

void dfs(int x,int y,int cost){
    if(x==n-1 && y==n-1){
    if(cost<min_cost){min_cost=cost;}
    std::cout<<"one loop got completed ------- giving cost :"<<cost<<" min cost :"<<min_cost<<std::endl;
    bool k = AllVisited();
    if(k==true){std::cout<<"found the elemeents !! yay "<<std::endl;  return;}
    //if(k==false){return;}
    }

    if(isSafe(x,y)==true){
          if(arr[x+1][y]!=0 && visited[x+1][y]==0){visited[x+1][y]=1; cost=cost+arr[x+1][y]; std::cout<<"sending xy:"<<x+1<<" "<<y<<" cost :"<<cost<<std::endl; dfs(x+1,y,cost); cost=cost-(arr[x+1][y]); visited[x+1][y]=0; std::cout<<"backtracking xy:"<<x+1<<y<<" cost :"<<cost<<std::endl;}
          if(arr[x][y+1]!=0 && visited[x][y+1]==0){visited[x][y+1]=1; cost=cost+arr[x][y+1]; std::cout<<"sending xy:"<<x<<" "<<y+1<<" cost :"<<cost<<std::endl; dfs(x,y+1,cost); cost=cost-(arr[x][y+1]); visited[x][y+1]=0; std::cout<<"backtracking xy:"<<x<<y+1<<" cost :"<<cost<<std::endl;}
          if(arr[x-1][y]!=0 && visited[x-1][y]==0){visited[x-1][y]=1; cost=cost+arr[x-1][y]; std::cout<<"sending xy:"<<x-1<<" "<<y<<" cost :"<<cost<<std::endl; dfs(x-1,y,cost); cost=cost-(arr[x-1][y]); visited[x-1][y]=0; std::cout<<"backtracking xy:"<<x-1<<y<<" cost :"<<cost<<std::endl;}
          if(arr[x][y-1]!=0 && visited[x][y-1]==0){visited[x][y-1]=1; cost=cost+arr[x][y-1]; std::cout<<"sending xy:"<<x<<" "<<y-1<<" cost :"<<cost<<std::endl; dfs(x,y-1,cost); cost=cost-(arr[x][y-1]); visited[x][y-1]=0; std::cout<<"backtracking xy:"<<x<<y-1<<" cost :"<<cost<<std::endl;}

    }
return ;
}


int main(){
int t;
std::cin>>t;

for(int tc=0;tc<t;tc++){
    std::cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            std::cin>>arr[i][j];
            visited[i][j]=0;
        }
    }
      min_cost=999;
      visited[0][0]=1;
      //min_cost=arr[0][0];
    dfs(0,0,arr[0][0]);
    //dfs(0,0,arr[0][0]);
    std::cout<<"min_cost"<<min_cost<<std::endl;
}

return 0;}



Correct largest no. in array with k swaps

#include<iostream>

using namespace std;
int arr[10];
int maxi[10];
int change;
int n;
int max_no;

void changeMax(){
    int x;
    for(int i=0;i<n;i++){ x=arr[i]+10*i; }
    int y;
    for(int i=0;i<n;i++){ x=maxi[i]+10*i; }
    if(y>x){
        max_no=y;
        for(int i=0;i<n;i++){ maxi[i]=arr[i]; }
    }
}

void swap(int i,int j){
      int t=arr[j];
        arr[j]=arr[i];
        arr[i]=t;
}

void findMaxno(int change){
if(change==0){return;}

for(int i=0;i<n;i++){
 for(int j=i+1;j<n;j++){
    //check if string badha hai toh change kardo
    if(arr[i]<arr[j]){
            std::cout<<"swapping i j"<<i<<" "<<j<<std::endl;
        //swap kardo
        swap(i,j);

     //find if no greater than max then change max
     changeMax();

     findMaxno(change--);

      swap(i,j);
    }
 }
}

}


int main(){
int t;
std::cin>>t;
for(int tc=1;tc<=t;tc++){
change=0;
std::cin>>n;
for(int i=0;i<n;i++){std::cin>>arr[i]; maxi[i]=arr[i]; max_no=0;}
std::cin>>change;
std::cout<<max_no<<std::endl;
}
return 0;}



No comments:

Post a Comment