D. 数独游戏2

传统 1000 ms 256 MiB
标准 IO
Special Judge

题目描述

数独是源自18世纪瑞士的一种数学游戏。玩家需要根据 9×99\times 9 盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫 3×33\times 3 内的数字均含 191\sim9,不重复。数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入 191\sim9 的数字,使 191\sim9 每个数字在每一行、每一列和每一宫中都出现且只出现一次,所以又称“九宫格”。

小 T 正在玩数独游戏。小 T 好不容易填完了一个数独,但他实在太粗心了,在 9×99\times 9 的盘面上居然有一个小格的数字是错误的!

聪明的你,能帮助小 T 纠正那个被填错的数字吗?

输入格式

输入数据共 99 行,每行 99 个用空格隔开的正整数,表示小 T 填写的数独方阵。

保证有且仅有一个位置的数字是错误的,且纠正这个数字后可以形成一个合法的数独方阵。

输出格式

输出一行 33 个用空格隔开的正整数 row,col,numrow,col,num,表示错误数字的行号、列号以及纠正后的数字。

样例

输入样例 1:

5 9 4 3 1 8 7 2 6
1 3 8 2 6 7 9 4 5
6 2 7 5 4 8 3 1 8
7 6 1 9 3 2 5 8 4
4 5 2 7 8 6 1 9 3
9 8 3 4 5 1 2 6 7
2 7 5 8 9 4 6 3 1
8 1 9 6 7 3 4 5 2
3 4 6 1 2 5 8 7 9

输出样例 1:

3 6 9