F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Problem 1186. -- [HNOI2007]胜负一子

1186: [HNOI2007]胜负一子

Time Limit: 10 Sec  Memory Limit: 162 MB
Submit: 32  Solved: 2
[Submit][Status][Discuss]

Description

五子棋是一种流传很广的棋类游戏,在一个15×15的棋盘上,对弈双方执黑白棋子(类似于围棋),执黑子者先下
,凡落下的棋子不能被提起,即不存在挪子和吃子的情况。为了简化问题,假设黑方不存在“禁手”,“禁手”是
五子棋术语,指禁止走棋子的地方。当某选手的棋子在横、竖、45度斜线方向、135度斜线方向之一先出现相连的5
个棋子时,该选手获胜。先考虑轮到黑棋走的一盘残局,请给出黑棋获胜的最少步数和在该步数下能获胜的所有不
同的下一步走法。

Input

共有15行,每行有15个由一个空格隔开的整数。
第i行,第j列的整数记做vij,用vij=0,1,2表示第i行,第j列的位置为空、有1黑子、有1白子,
从左上角开始,按从左至右,自上而下的顺序输入,
即输入的第1行第1列整数v11表示第1行第1列位置的状态,
输入的第15行第15列整数v15,15表示第15行第15列位置的状态。

Output

第一行为两个整数a和b,
其中:a表示黑棋获胜的最少步数,b表示黑棋在a步获胜的所有不同的下一步走法的种数。
从第二行到第b+1行,每行有两个整数,
分别表示黑棋在a步获胜的一种下一步走法落子位置的行数i和列数j,
要求这些走法按照15i+j的大小从小到大排列。

Sample Input

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 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 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 0 2 0 2 0 0 0 0 0
0 0 0 0 0 0 2 1 1 2 0 0 0 0 0
0 0 0 0 0 0 0 1 2 1 0 0 0 0 0
0 0 0 0 0 0 2 1 1 1 1 2 0 0 0
0 0 0 0 0 0 0 1 0 1 0 1 0 0 0
0 0 0 0 0 0 2 2 0 1 1 0 2 0 0
0 0 0 0 0 0 0 0 0 2 0 2 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 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output

3 2
10 9
10 11

HINT

Source

数据由SillyHook生成

[Submit][Status][Discuss]

HOME Back