Description
为了准备期末考试了，laprovence正被讨厌的数字逻辑搞的头昏脑胀，尤其后面的一堆乱七八糟的概念，简直不知所云@#~！*&~
这不有道简单的题就把他给难住了，题目大意是这样的：给出n个发光二极管，每个二极管都有两种状态，亮（on）与灭（off），然后给出一组每两个二极管之间的约束关系，
约束关系有以下3 种
1）a and b 表示第a个与第b个二极管必须同时亮
2）a or b表示第a个与第b个二极管至少有一个亮
3）a xor b 表示第a个与第b个二极管必须是一个亮，一个灭
Input
第一行两个整数n（二极管的个数，n<=10），m（m组约束关系，m<=50）
然后m行约束关系以a and b，a or b，a xor b的形式给出
多组测试数据，当n=0，m=0时结束
Output
输出每个二极管的状态（一行,每两个状态之间用空格隔开，最后一个不要空格，保证只有一组解），如果没有解输出No solution
Sample Input
2 1
1 and 2
3 3
1 and 2
2 xor 3
1 and 3
0 0
Sample Output
on on
No solution
Source
laprovence@AMMKPAL
#include<stdio.h>
#include<string.h>
int map[11][11];
bool f[11];
int m,n;
bool flag;
void dfs(int depth)
{
int i,j;
bool fi=true;
if(depth>n&&!flag)
{
for(i=1;i<=n&&fi;i++)
for(j=1;j<=n&&fi;j++)
if(i!=j)
{
if(map[i][j]==1)
{
if(!f[i]||!f[j])
{
fi=false;
break;
}
}
if(map[i][j]==2)
{
if(!f[i]&&!f[j])
{
fi=false;
break;
}
}
if(map[i][j]==3)
{
if((!f[i]&&!f[j])||(f[i]&&f[j]))
{
fi=false;
break;
}
}
}
if(fi)
{
flag=true;
for(i=1;i<=n;i++)
{
if(i!=1) printf(" ");
if(f[i]) printf("on");
else printf("off");
}
printf("/n");
}
return;
}
if(!flag)
{
f[depth]=true;
dfs(depth+1);
}
if(!flag)
{
f[depth]=false;
dfs(depth+1);
}
}
int main()
{
int i,j,a,b;
char str[10];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(scanf("%d%d",&n,&m)!=EOF)
{
flag=false;
memset(map,0,sizeof(map));
memset(f,false,sizeof(f));
if(n==0&&m==0) break;
for(i=1;i<=m;i++)
{
scanf("%d ",&a);
scanf("%s ",str);
scanf("%d ",&b);
if(strcmp(str,"and")==0)
map[a][b]=1;
else
if(strcmp(str,"or")==0)
map[a][b]=2;
else
map[a][b]=3;
}
dfs(1);
if(!flag) printf("No solution/n");
}
return 0;
}