算法设计与分析 棋盘覆盖.doc
需积分: 12 66 浏览量
2022-01-03
00:01:02
上传
评论
收藏 23KB DOC 举报
棋盘覆盖问题实验报告
问题描述与实验目的：
设 n=2
k
（k≥0）。在一个 n×n 个方格组成的棋盘中，恰有 1 个方格与其
他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置
有 4
k
种，因而有 n
2
种不同的棋盘，下图所示是 k=2，n=4 时 16 种棋盘中的
一个。
棋盘覆盖问题要求用下图所示的 4 种不同形状的 L 型骨牌覆盖给定棋盘上
除特殊方格以外的所有方格，且任何 2 个 L 型骨牌不得重叠覆盖。
易知，在任何一个 n×n 的棋盘中，用到的 L 型骨牌个数恰为 (n
2
-1)/3 。
你的任务是给定 k>1，n=2
k
设计一个算法实现棋盘的一种覆盖。
输入
测试数据有若干行，每行 3 个整数 k，x，y，其中 n=2
k
是棋盘的规模，
(x，y)是特殊方格的位置坐标，（k>1）。
输出
对输入中的每个正整数 k，第一行上先输出“Case #: n=”，接着输出 n 的
值，其中#是测试数据的序号，从 1 开始。第 2 到第 n+1 行，输出对于规模为
n=2
k
的棋盘的一个覆盖。在该棋盘覆盖中，同一个骨牌用 3 个相同的数字表示。
各骨牌表示的数字从 1 开始编号。特殊方格用#表示。
输入样例
1 2 1
2 2 3
资源评论
