Description
你有n个砝码，均为1克，2克或者3克。你并不清楚每个砝码的重量，但你知道其中一些砝码重量的大小关系。你把其中两个砝码A和B放在天平的左边，需要另外选出两个砝码放在天平的右边。问：有多少种选法使得天平的左边重(c1)、一样重(c2)、右边重(c3)？（只有结果保证惟一的选法才统计在内)
暴力枚举，暴力判断
#include<cstdio>
#include<algorithm>
#include<cstring>
#define PROC "scale"
using namespace std;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
typedef long long LL;
int n, a, b;
const int maxn=52, inf=0x3f3f3f3f;
char mp[maxn][maxn];
int belong[maxn], bn;
struct yjq{
int rel[maxn];
bool able[4];
yjq()
{
memset(able,true,sizeof(able));
memset(rel,0x3f,sizeof(rel));
}
};
yjq naive[maxn];
int fa[maxn];
int findfa(int son)
{
if (son!=fa[son]) fa[son]=findfa(fa[son]);
return fa[son];
}
void addfa(int s1, int s2)
{
int f1=findfa(s1), f2=findfa(s2);
fa[f2]=f1;
}
void init()
{
bn=n;
for (int i=1; i<=n; i++)
fa[i]=i;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
if (mp[i][j]=='=')
{
addfa(i,j);
}
}
}
for (int i=1; i<=n; i++)
belong[i]=findfa(i);
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
if (mp[i][j]=='-')
{
naive[belong[i]].rel[belong[j]]=1;
naive[belong[i]].able[3]=0;
naive[belong[j]].rel[belong[i]]=-1;
naive[belong[j]].able[1]=0;
}
else if (mp[i][j]=='+')
{
naive[belong[i]].rel[belong[j]]=-1;
naive[belong[i]].able[1]=0;
naive[belong[j]].rel[belong[i]]=1;
naive[belong[j]].able[3]=0;
}
}
}
for (int i=1; i<=bn; i++)
{
for (int j=1; j<=bn; j++)
{
for (int k=1; k<=bn; k++)
{
if (naive[i].rel[j]==1&&naive[i].rel[j]==naive[j].rel[k])
{
naive[i].rel[k]=2;
naive[i].able[2]=0;
naive[k].rel[i]=-2;
naive[k].able[2]=0;
}
}
}
}
}
int cnt[4];
int getres(int num1, int num2)
{
if (num1>num2) return 1;
if (num1<num2) return 3;
return 2;
}
int st[5], sw[5];
bool illegal(int s1, int s2, int s3, int s4, int w1, int w2, int w3, int w4)
{
st[1]=belong[s1];
st[2]=belong[s2];
st[3]=belong[s3];
st[4]=belong[s4];
sw[1]=w1;
sw[2]=w2;
sw[3]=w3;
sw[4]=w4;
for (int i=1; i<=4; i++)
{
if (!naive[st[i]].able[sw[i]]) return 1;
for (int j=i+1; j<=4; j++)
{
if (st[i]==st[j]&&sw[i]!=sw[j]) return 1;
int delta=naive[st[i]].rel[st[j]];
if (delta==inf) continue;
if (delta>0)
{
if (sw[i]+delta>sw[j]) return 1;
}
else
{
if (sw[i]+delta<sw[j]) return 1;
}
}
}
return 0;
}
void solve()
{
for (int c=1; c<n; c++)
{
if (c==a||c==b) continue;
for (int d=c+1; d<=n; d++)
{
if (d==a||d==b||d==c) continue;
int res=0;
for (int w1=1; w1<=3; w1++)
{
for (int w2=1; w2<=3; w2++)
{
for (int w3=1; w3<=3; w3++)
{
for (int w4=1; w4<=3; w4++)
{
if (illegal(a,b,c,d,w1,w2,w3,w4)) continue;
// printf("%d:%d %d:%d %d:%d %d:%d\n",a,w1,b,w2,c,w3,d,w4);
int back=getres(w1+w2,w3+w4);
if (back!=res && res!=0)
{
res=-1;
break;
}
if (!res) res=back;
}
}
}
}
if (res!=-1)
cnt[res]++;
}
}
}
int main()
{
// freopen(PROC".in","r",stdin);
// freopen(PROC".out","w",stdout);
scanf("%d%d%d",&n,&a,&b);
for (int i=1; i<=n; i++)
scanf("%s",&mp[i][1]);
init();
solve();
for (int i=1; i<=2; i++)
printf("%d ",cnt[i]);
printf("%d\n",cnt[3]);
fclose(stdout);
return 0;
}
