Preparing NOJ

独立钻石跳棋问题

1000ms 65536K

Description:


独立钻石跳棋的棋盘上有33 个方格,每个方格中可放1 枚棋子。棋盘中最多可摆放32枚棋子。下棋的规则是任一棋子可以沿水平或垂直方向跳过与其相邻的棋子进入空着的方格并吃掉被跳过的棋子。试设计一个算法,对于任意给定的棋盘布局,找出一种下棋方法,使得最终棋盘上只剩下一个棋子。

对于给定的独立钻石跳棋的棋盘初始布局,和棋盘上最终剩下的棋子所在的位置(x,y),编程计算一种遵循下棋的规则下棋方法,使最终棋盘上仅在位置(x,y)处有一枚棋子。当(x,y)=(0,0)时,表示不指定棋子的最终位置。棋子位置的坐标定义如下。

Input:

文件的第一行中有1个正整数n,表示棋盘的初始布局中有n个棋子。第2 行起每行2 个数,分别是n个棋子的位置。最后1 行是棋盘上最终剩下的棋子所在的位置。

Output:

每行有2 对方格坐标(a,b)(c,d),表示从方格(a,b)跳到方格(c,d)。问题无解时输出“Nosolution!

Sample Input:

8
4 1
5 2
5 3
6 3
3 4
4 4
4 5
4 6
0 0

Sample Output:

(3,4) (5,4)
(4,6) (4,4)
(4,4) (6,4)
(6,4) (6,2)
(6,2) (4,2)
(4,1) (4,3)
(5,3) (3,3)

Note:

undefined

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1289

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet