Nowcoder Practice 61 C.四个选项

题目传送门

题意：给定12个选择题，限定每个选项个数，和若干个两两相等的选项。求方案数

思路：由于只有12个，可以使用DFS，对每个题一边搜索一边判重。

#include<bits/stdc++.h>
using namespace std;
int a[20][20],b[5],c[5],d[20],m,ans;
void dfs(int id){
	 if(id>12){
	 	ans++;
	 	return;
	 }
	 for(int i=1;i<=4;i++)
	 	  if(c[i]<b[i]){ //当前颜色个数小于目标颜色个数 
	 	  		int f=1;
	 	  		for(int j=1;j<id;j++){//判重 
	 	  				if(a[j][id]&&d[j]!=i)
	 	  				{
	 	  					f=0;
							break;	
						}
				   }
				if(!f) continue;
				c[i]++;
				d[id]=i;
				dfs(id+1);
				c[i]--;//回溯 
		   }
}
int main(){
	for(int i=1;i<=4;i++) scanf("%d",&b[i]);
	scanf("%d",&m);
	for(int i=1,x,y;i<=m;i++)
		scanf("%d%d",&x,&y),a[x][y]=a[y][x]=1; 
	dfs(1);
	printf("%d\n",ans);
	return 0;
}