NC14304. Square Network
描述
输入描述
The first line is the number of test cases.
For each test case, the first line consists of three integers N, K, and T (N, K ≤ 6, T≤ 12).
In the next N lines, each line consists of N integers Ai,j.If Ai,j = -1, the blank (i, j) must be empty. If Ai,j = 0, a server is require to put on this blank. Otherwise, a server of type Ai,j is on this blank.
In the next T lines, each line consists of K pair of integers. Each pair of integers donate the coordinate of blank in this group.
输出描述
For each test case, output an integer donating the ways that Alice and Bob can arrange the room. If the solution is larger than 20172017, output `TOO MANY`.
示例1
输入:
2 3 3 4 0 0 1 0 -1 0 0 0 0 1 1 1 2 1 3 1 1 2 1 3 1 1 3 2 3 3 3 3 1 3 2 3 3 5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
输出:
6 TOO MANY
C++11(clang++ 3.9) 解法, 执行用时: 1865ms, 内存消耗: 5160K, 提交时间: 2020-03-10 21:18:08
#include<cstdio>
#include<cstring>
const int MAXN=12;
const int MAXT=100;
const int MAXP=1100;
const int LIMIT=20172017;
const int MAXD=1100;
int N,M;
int head,cnt;
int L[MAXD];
int R[MAXD];
int U[MAXD];
int D[MAXD];
int H[MAXD];
int C[MAXD];
int S[MAXD];
int ROW[MAXD];
int ANS;
int A[MAXD][MAXD];
void insert(int i,int j)
{
C[++cnt]=j;
S[j]++;
D[cnt]=j;
U[cnt]=U[j];
if(H[i]) R[cnt]=H[i],L[cnt]=L[H[i]];
else R[cnt]=L[cnt]=cnt;
H[i]=cnt;
U[D[cnt]]=cnt;
D[U[cnt]]=cnt;
R[L[cnt]]=cnt;
L[R[cnt]]=cnt;
}
void remove(int c)
{
R[L[c]]=R[c];
L[R[c]]=L[c];
for(int i=D[c];i!=c;i=D[i])
for(int j=R[i];j!=i;j=R[j])
{
U[D[j]]=U[j];
D[U[j]]=D[j];
S[C[j]]--;
}
}
void resume(int c)
{
for(int i=U[c];i!=c;i=U[i])
for(int j=L[i];j!=i;j=L[j])
{
D[U[j]]=j;
U[D[j]]=j;
S[C[j]]++;
}
L[R[c]]=R[L[c]]=c;
}
void dance()
{
if(ANS>LIMIT) return;
if(R[head]==head)
{
++ANS;
return;
}
int s=0x7FFFFFFF,c;
for(int i=R[head];i!=head;i=R[i])
if(S[i]<s) s=S[i],c=i;
remove(c);
for(int i=D[c];i!=c;i=D[i])
{
for(int j=R[i];j!=i;j=R[j]) remove(C[j]);
dance();
for(int j=L[i];j!=i;j=L[j]) resume(C[j]);
}
resume(c);
}
void initd()
{
cnt=M;
for(int i=0;i<=M;i++)
{
C[i]=U[i]=D[i]=i;
L[i+1]=i;
R[i]=i+1;
S[i]=0;
}
L[0]=M;
R[M]=0;
for(int i=1;i<=N;i++)
{
H[i]=0;
for(int j=1;j<=M;j++)
{
if(A[i][j]) insert(i,j);
}
}
}
int n,k,t,b;
int a[MAXN][MAXN];
int c[MAXP];
int l[MAXP];
void init()
{
scanf("%d %d %d",&n,&k,&t);
b=0;
int cl=0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%d",&a[i][j]);
if(a[i][j]==0)
{
c[++b]=0;
a[i][j]=b;
l[b]=cl;
cl+=k;
}
else if(a[i][j]>0)
{
c[++b]=a[i][j];
a[i][j]=b;
l[b]=cl;
cl++;
}
}
N=cl;
M=b+t*k;
memset(A,0,sizeof(A));
for(int i=1;i<=b;++i)
{
if(c[i]==0)
{
for(int j=1;j<=k;++j)
A[l[i]+j][i]=1;
}
else
{
A[l[i]+1][i]=1;
}
}
for(int i=1;i<=t;++i)
{
int x,y;
for(int j=1;j<=k;++j)
{
scanf("%d %d",&x,&y);
int bb=a[x][y];
if(c[bb]==0)
{
for(int j2=1;j2<=k;++j2)
A[l[bb]+j2][b+(i-1)*k+j2]=1;
}
else
{
A[l[bb]+1][b+(i-1)*k+c[bb]]=1;
}
}
}
}
void solve()
{
ANS=0;
initd();
dance();
if(ANS>LIMIT) printf("TOO MANY\n");
else printf("%d\n",ANS);
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
init();
solve();
}
return 0;
}