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;}
#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