Gym 100952E&&2015 HIAST Collegiate Programming Contest E. Arrange Teams【DFS+剪枝】

E. Arrange Teams

time limit per test:2 seconds

memory limit per test:64 megabytes

input:standard input

output:standard output

Syrian Collegiate Programming Contest (SCPC) is the qualified round for the Arab Collegiate Programming Contest. Each year SCPC organizers face a problem that wastes a lot of time to solve it, it is about how should they arrange the teams in the contest hall.

Organizers know that they have t teams and n*m tables allocated in n rows and m columns in the contest hall. They don't want to put teams in a random way. Each year SCPC chief judge puts a list of paired teams (list of a,b teams) that should not sit next to each other (because they are so good or so bad!).

if pair (a,b) is in chief judge list, this means that:

- team number a should not sit in-front of team number b

- team number b should not sit in-front of team number a

- team number a should not sit right to team number b

- team number b should not sit right to team number a

Organizers wastes a lot of time to find a good team arrangement that satisfy all chief judge needs. This year they are asking you to write a program that can help them.

Input

First line contains number of test cases. The first line in each test case contains three numbers: (1  ≤  n,m  ≤  11) and (1  ≤  t  ≤  10). Second line in each test case contains (0  ≤  p  ≤  40) number of pairs. Then there are p lines, each one of them has two team numbers a and b (1  ≤  a,b  ≤  t) where a is different than b.

Output

For each test case, print one line contains the total number of teams arrangements that satisfy all chief judge needs (We guarantee that it will be less than 9,000,000 for each test case). If there is no suitable arrangements print "impossible".

Examples

Input

2
1 3 2
1
1 2
2 2 4
2
1 2
1 3

Output

2
impossible

Note

In test case 1 there are 2 teams and 3 tables in one row at the contest hall. There are only one pair (1,2), so there are 2 solutions:

team1 then empty table then team2

team2 then empty table then team1

In test case 2 there are 4 tables in 2 rows and 2 columns, and there are 4 teams. There is no arrangement that can satisfy chief judge needs.

题目链接:http://codeforces.com/gym/100952/problem/E

分析:dfs、剪枝

首先用dp[vis[a][b]][k]布尔数组双向的记录那些vis[i][j-1],vis[i][j+1],vis[i-1][j],vis[i+1][j];a=i-1,i+1,i,i;b=j,j,j-1,j+1;

然后inline void dfs(int k)表示当前正在处理队伍k,然后遍历所有i, j如果没有访问过,并且满足条件则dfs(k + 1)

直到顺利的把所以的t个队伍都填进去了,那一个分枝才ans++; return;

剪枝以后的复杂度不大算的出来,但看数据大小 (1  ≤  n,m  ≤  11) and (1  ≤  t  ≤  10) 这样做一般可以AC

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 inline int read()
 4 {
 5     int x=0,f=1;
 6     char ch=getchar();
 7     while(ch<'0'||ch>'9')
 8     {
 9         if(ch=='-')
10             f=-1;
11         ch=getchar();
12     }
13     while(ch>='0'&&ch<='9')
14     {
15         x=x*10+ch-'0';
16         ch=getchar();
17     }
18     return x*f;
19 }
20 inline void write(int x)
21 {
22     if(x<0)
23     {
24         putchar('-');
25         x=-x;
26     }
27     if(x>9)
28         write(x/10);
29     putchar(x%10+'0');
30 }
31 int n,m,t,ans;
32 int vis[15][15];
33 bool dp[15][15];
34 inline void DFS(int k)
35 {
36     if(k==t+1)
37     {
38         ans++;
39         return;
40     }
41     for(int i=1;i<=n;i++)
42     {
43         for(int j=1;j<=m;j++)
44         {
45             if(vis[i][j])
46                 continue;
47             if(!dp[vis[i-1][j]][k]&&!dp[vis[i+1][j]][k]&&!dp[vis[i][j-1]][k]&&!dp[vis[i][j+1]][k])
48             {
49                 vis[i][j]=k;
50                 DFS(k+1);
51                 vis[i][j]=0;
52             }
53         }
54     }
55 }
56 int main()
57 {
58     int T,q,x,y;
59     T=read();
60     while(T--)
61     {
62         ans=0;
63         memset(dp,0,sizeof(dp));
64         memset(vis,0,sizeof(vis));
65         n=read();
66         m=read();
67         t=read();
68         q=read();
69         for(int i=0;i<q;i++)
70         {
71             x=read();
72             y=read();
73             dp[x][y]=1;
74             dp[y][x]=1;
75         }
76         DFS(1);
77         if(ans!=0)
78             write(ans),printf("\n");
79         else printf("impossible\n");
80     }
81     return 0;
82 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏linux、Python学习

数据可视化:Matplotlib的坐标轴管理

有兴趣的可以跟踪pyplot模块的figure函数,可以完整看见Figure的创建过程,由FigureManager创建与管理的。

56400
来自专栏java 成神之路

java.util.Random 实现原理

35350
来自专栏应兆康的专栏

100个Numpy练习【4】

翻译:YingJoy 网址: https://www.yingjoy.cn/ 来源: https://github.com/rougier/numpy-100...

48680
来自专栏聊聊技术

原 "二分查找(Binary Search

441110
来自专栏丁科的专栏

Pytorch 学习笔记之自定义 Module

pytorch 是一个基于 python 的深度学习库。pytorch 源码库的抽象层次少,结构清晰,代码量适中。相比于非常工程化的 tensorflow,py...

4.5K20
来自专栏决胜机器学习

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十一)——图的连通性问题与最小生成树算法(1) (原创内容,转载请注明来源,谢谢) 一、连通分量和生成树 1、无向图 设E(G)为连通图G的所...

49990
来自专栏灯塔大数据

每周学点大数据 | No.5算法的分析之图灵机

No.5期 算法的分析之图灵机 小可:那计算机科学有没有对易解和难解问题进行一个相对严格的界定呢? Mr. 王:有的,这里既然提到了多项式算法和易解难解问题,...

38580
来自专栏Code_iOS

OpenGL ES 2.0 (iOS)[03]:熟练图元绘制,玩转二维图形

文章的大前提是,你得有《OpenGL ES 2.0 (iOS): 一步从一个小三角开始》的基础知识。

22810
来自专栏编程

数控宏程序的编程及应用

1. 什么场合会用到宏程序编程? 其实说起来宏就是用公式来加工零件,比如说椭圆,如果没有宏的话,我们要逐点算出曲线上的点,然后慢慢来用直线逼近,如果是个光洁度要...

21480
来自专栏数据结构与算法

HDU4352 XHXJ's LIS(LIS 状压)

刚开始的思路是$f[i][j]$表示到第$i$位,LIS长度为$j$的方案。 然而发现根本不能转移,除非知道了之前的状态然后重新dp一遍。。

10330

扫码关注云+社区

领取腾讯云代金券