#P3192. [HNOI2007] 胜负一子

[HNOI2007] 胜负一子

题目描述

五子棋是一种流传很广的棋类游戏,在一个 15×1515\times 15 的棋盘上,对弈双方执黑白棋子(类似于围棋),执黑子者先下,凡落下的棋子不能被提起,即不存在挪子和吃子的情况。

为了简化问题,假设黑方不存在“禁手”,“禁手”是五子棋术语,指禁止走棋子的地方。当某选手的棋子在横、竖、4545 度斜线方向、135135 度斜线方向之一先出现相连的 55 个棋子时,该选手获胜。

先考虑轮到黑棋走的一盘残局,请给出黑棋获胜的最少步数和在该步数下能获胜的所有不同的下一步走法。

输入格式

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

输出格式

第一行为两个整数 aabb,其中:aa 表示黑棋获胜的最少步数,bb 表示黑棋在 aa 步获胜的所有不同的下一步走法的种数。

从第二行到第 b+1b+1 行,每行有两个整数,分别表示黑棋在 aa 步获胜的一种下一步走法落子位置的行数 ii 和列数 jj,要求这些走法按照 15×i+j15\times i+j 的大小从小到大排列。

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
3 2
10 9
10 11