Please help review my code, not sure its working as intended.... its in C! Objective Give practice with Recursion in C. Give practice with Backtracking in C. Give practice with Stacks in C. Input will begin with a line containing 2 integers, n and c (1 ≤ n ≤ 20; 0 ≤ c ≤ n choose 2), representing the number of animal exhibits and the number of constraints. The following c lines
Please help review my code, not sure its working as intended.... its in C!
Objective
Give practice with Recursion in C.
Give practice with Backtracking in C.
Give practice with Stacks in C.
Input will begin with a line containing 2 integers, n and c (1 ≤ n ≤ 20; 0 ≤ c ≤ n choose 2),
representing the number of animal exhibits and the number of constraints. The following c lines
will each contain a constraint description in the form of 3 space separated integers, f, s, and d
(1 ≤ f, s ≤ n; f ≠ s; 0 ≤ c ≤ n - 2), representing the index of the first animal, the index of the
second animal, and the exact number of cages that should be in between those 2 animals.
For 7 of the 10 cases each animal will be in at most 1 constraint.
Output should contain 1 line. In the event that a solution exists, you should print out n space
separated integers representing the animal index given in order from the first cage to the last. If
there is no solution the output should be only the phrase “No Solution.” (quotes for clarity).
| Sample Input | Sample output |
|
4 2 1 2 1 3 4 0 |
No Solution |
| Sample Input | Sample Output |
| 5 4 1 2 1 1 3 1 1 5 0 2 5 2 |
2 4 1 5 3 |
My code below:
#include<stdio.h>
#include<limits.h>
// ans variable will store the minimum noise generated
int ans=INT_MAX;
// swap function
void swap(int *a, int *b){
int tmp=*a;
*a=*b;
*b=tmp;
}
// min and max function
int min(int a,int b){
if(a<=b) return a;
else return b;
}
int max(int a,int b){
if(a<=b) return b;
else return a;
}
// recursive function generates all possible arrangement of the animals
void recursive(int ch[],int pos,int n,int noise[n][n]){
// for each possible arrangement
if(pos==n){
// we calculate noise generated for this arrangement
int tmp=0;
for(int i=0;i<n;i++){
for(int j=max(0,i-2);j<=min(n-1,i+2);j++){
tmp+=noise[ch[i]-1][ch[j]-1];
}
}
// we can recheck if ans variable stores minimum possible value of noise generation
ans=min(ans,tmp);
return;
}
else{
// Using backtracking for generated all permutation
for(int j=pos;j<n;j++){
swap(&ch[j],&ch[pos]);
recursive(ch,pos+1,n,noise);
// backtracking
swap(&ch[j],&ch[pos]);
}
}
}
int main(){
// taking input from the user
int n;
scanf("%d",&n);
int noise[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&noise[i][j]);
}
}
// ch array will store the position of the animals
int ch[n];
int pos=0;
for(int i=1;i<=n;i++){
ch[i-1]=i;
}
// calling our recursive function
recursive(ch,0,n,noise);
// output the minimum possible answer
printf("The minimum noise generated is : %d",ans);
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
