uoj#P225. 【UR #15】奥林匹克五子棋
【UR #15】奥林匹克五子棋
各位观众,各位观众,您现在收看的是第 666 届跳蚤奥运会的比赛现场。在刚刚的跳高比赛中,天才跳高小将“最强跳蚤”靠着“最强跳蚤跳跳跳”和经验丰富的伏特跳蚤国王大战了三天三夜,最后战成 $233:233$ 平。考虑到迟迟不能决出胜者,比赛组委会决定临时更换比赛项目,而被选中的则是在跳蚤大陆流行已久的游戏——五子棋。
五子棋是 Picks 博士发明的一款益智类游戏。为了加大难度,这里的五子棋实则是 “$k$ 子棋”。
游戏规则很简单,游戏双方分别使用黑白两色的棋子,下在 $n \times m$ 的棋盘上,先形成 $k$ 子连成一条直线的一方获胜。即,若己方有连续的 $k$ 个棋子形成方向为上下、左右、左上右下、左下右上四个方向之一的直线,就可以获得胜利。
但没想到的是,“最强跳蚤”和伏特跳蚤国王不仅跳得比谁都高,知识水平也是不相上下。啊我们看到,在第 66 局他们再一次打成了平局……
现在是我们的有奖竞猜环节!大家可以来猜猜下一个平局是怎么产生的呢?最早给出答案的观众可以获得小火车一列哦。
现在,你作为一名观众想参与到竞猜环节中。但首先,你需要构造一个下棋过程使得填满整个棋盘之后也没有连续 $k$ 个同色棋子在这四个方向上排成一条直线。
注意,$n \times m$ 可能为奇数,此时先手会比后手多下一步棋。
输入格式
第一行三个正整数 $n,m,k$,意义如前所述。
输出格式
如果双方不能打成平局,输出 $-1$;
否则输出 $n \times m$ 行,第 $i$ 行两个整数 $x_i, y_i$ 表示第 $i$ 次落子的坐标为第 $x_i$ 行第 $y_i$ 列。黑子先行,所以 $i$ 为奇数时为黑方落子,$i$ 为偶数时白方落子。坐标需满足 $1 \le x_i \le n, 1 \le y_i \le m$。
4 4 3
1 2
1 1
1 4
1 3
2 1
2 3
2 2
2 4
3 3
3 2
3 4
3 1
4 1
4 4
4 3
4 2
样例一的参考输出最终得到的棋盘如下:
1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1
其中 0 为先手,1 为后手。
2 3 3
1 1
2 1
2 2
1 2
1 3
2 3
限制与约定
由于一些原因,本题使用捆绑测试。每个子任务有若干个测试点,分为 $4$ 个子任务,你只有通过一个子任务的所有测试点才能得到这个子任务的分数。
子任务 | 分值 | 限制 |
---|---|---|
1 | 30 | $2 \leq n,m \leq 4$ |
2 | 15 | $\min(n,m) = 1$ |
3 | 15 | $n,m \ge 2, \min(n,m) \lt k$ |
4 | 40 | $n,m \ge 2$ |
在所有数据中,都满足 $1 \leq k \leq 10^9$ 且 $1 \le n,m \le 500$。
时间限制:$1\texttt{s}$
空间限制:$256\texttt{MB}$