BZOJ 2954: [Poi2002]超级马(bfs)

Description

在一个无限的棋盘上有一个超级马,它可以完成各种动作。每一种动作都是通过两个整数来确定——第一个数说明列的数(正数向右,负数向左),第二个数说明行的数(正数向右,负数向左),移动马来完成这个动作。
任务
       编写一个程序
²        输入说明各种超级马的数据库。
²        对每一个超级马进行确认,是否通过自己的行动可以到达盘面上的每一个区。

Input

第一行中存在一个整数K,它代表数据库的数1<=k<=100。在这个数字后出现K数据库。它们的每一个第一行中会出现整数N,它是马能够完成的各种动作的数,1<=n<=100。接下来数据库的每一个行中包含两个整数P和Q,它们由单个空格分开,说明动作,-100<=p, q<=100。

Output

应由K行组成,当第I个数据库的超级马可以到达盘面的每一个区,第I行应包含一个词TAK,而另一个词NIE则恰恰相反。

Sample Input

2

3
1 0
0 1
-2 -1
5
3 4
-3 -6
2 -2
5 6
-1 4

Sample Output

TAK
NIE
可以把每个操作看成向量,那么如果要整个平面都可达,那么只要可以凑出(0,1),(0,-1),(1,0),(-1,0)这四个单位向量就肯定可以。标算是数论方面的,然而弱根本不会写,于是就写了bfs。一开始T了,加个剪枝就过了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注