407843: GYM102899 L KK 学五子棋

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. KK 学五子棋time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

有一天 kk 一个人在研究残局,现在他得到了一个五子棋的残局,当前轮到黑色方下子,他在思考:

  • 他能否在这一步内胜利? 如果能,那么他需要把棋子下在哪儿?
  • 他若在这一步内不能胜利,那么他把棋子下在哪儿,使得对方不能在下一步获胜?

此处我们约定,五子棋获胜条件为:

当某一方落子后,这一方有大于等于 $$$5$$$ 颗相同颜色的棋子在一条线上(可以为横连、纵连、斜连),那么该方获胜。

Input

多组数据评测。

第一行包含一个正整数 $$$T(1 \leq T \leq 10^2)$$$,表示有 $$$T$$$ 组数据。

对于每一组数据:

第一行包含两个正整数 $$$n, m(5 \leq n, m \leq 10^3)$$$,表示棋盘的大小。

接下来 $$$n$$$ 行,每行 $$$m$$$ 个整数 $$$a_i(0 \leq a_i \leq 2)$$$,表示该位置的棋子状态。

  • $$$0$$$ 表示该位置为空
  • $$$1$$$ 表示该位置为白棋
  • $$$2$$$ 表示该位置为黑棋

数据保证 $$$\sum n \cdot m \leq 10^6$$$。

数据保证当前局面下白棋和黑棋的数量一样多。

数据保证棋盘中 $$$0$$$ 的个数大于等于 $$$2$$$。

数据保证当前局面是非胜利局面,即没有五个白棋连子,也没有五个黑棋连子。

Output

如果 KK 能够在这一步内胜利(输出包含两行):

第一行输出 "Win"(没有引号)。

第二行输出包含两个以空格分割的正整数 $$$x \; y(1 \leq x \leq n, 1 \leq y \leq m)$$$,表示 KK 在这一步要下的棋子的位置。

如果有多个解,那么输出 $$$x$$$ 最小的解,如果还有多解,输出 $$$y$$$ 最小的解。

如果 KK 不能够在这一步内胜利,但是可以使得对方不能在下一步内胜利(输出包含两行):

第一行输出 "Defense"(没有引号)。

第二行输出包含两个以空格分割的正整数 $$$x \; y(1 \leq x \leq n, 1 \leq y \leq m)$$$,表示 KK 在这一步要下的棋子的位置。

如果有多个解,那么输出 $$$x$$$ 最小的解,如果还有多解,输出 $$$y$$$ 最小的解。

否则,kk 在这一步不管怎么下,对方都可以在下一步胜利(输出包含一行):

第一行输出 "Defeated"(没有引号)。

ExampleInput
2
5 6
0 0 0 0 2 0
0 0 1 0 2 2
0 0 0 1 0 2
0 0 0 0 1 0
0 0 0 0 0 1
5 10
1 1 0 2 0 0 0 2 0 0
1 1 0 0 2 0 2 0 0 0
1 1 0 0 0 0 0 0 0 0
1 1 0 0 2 0 2 0 0 0
0 0 0 2 0 0 0 2 0 0
Output
Defense
1 2
Win
3 6

加入题单

上一题 下一题 算法标签: