-->
当前位置:首页 > 题库 > 正文内容

7-6 棋盘覆盖 (10 分)

Luz3年前 (2021-03-20)题库1577
7-6 棋盘覆盖 (10 分)

在一个2^k * 2^k(k为正整数,k<=10,length=2^k)个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格(其坐标为aa,bb,分别代表行坐标号和列坐标号),以及有四种L型骨牌(如下图)。求用若干块这种L型骨牌实现除该特殊点棋盘的全覆盖。(本题要求采用分治算法做)

输入格式:

输入三个数,分别是aa,bb,length.

输出格式:

输出整个棋盘。其中特殊方格填为0,然后铺棋盘的顺序为:先铺四个子棋盘交界的部分,然后递归的对每个子棋盘按照左上,右上,右下,左下的顺时针顺序铺满棋盘。每一块骨牌中三个方格数字相同,按照顺序标号,即第一块骨牌全标为1,第二块骨牌全标为2,...,以此类推。输出的每个数占4个场宽,右对齐。

输入样例:

1 1 4

表示:特殊格子为(1,1),棋盘有4行4列。

输出样例:

   0   2   3   3
  2   2   1   3
  5   1   1   4
  5   5   4   4

表示:先铺三个1(一块L型骨牌),再铺三个2,...,最后铺三个5.


#include<bits/stdc++.h>
using namespace std;

int num[100][100]; 
int cnt=1;

void chess(int x,int y,int aa,int bb,int length)
{
	if(length == 1)
	{
		return;
	}
	int t = cnt++;
	int half = length/2;
	
	if(aa < x+half && bb < y+half)
	{
		chess(x, y, aa, bb, half);
	}
	else
	{
		num[x+half-1][y+half-1]=t; 
		chess(x, y, x+half-1, y+half-1, half); 
	} 
	
	if(aa < x+half && bb >= y+half)
	{
		chess(x, y+half, aa, bb, half);
	}
	else
	{
		num[x+half-1][y+half]=t;
		chess(x, y+half, x+half-1, y+half, half);
	}
	 
	if(aa >= x+half && bb >= y+half) 
	{
		chess(x+half, y+half, aa, bb, half);
	}
	else
	{
		num[x+half][y+half]=t; 
		chess(x+half, y+half, x+half, y+half, half);
	}
	
	if(aa >= x+half && bb < y+half)
		chess(x+half, y, aa, bb, half); 
	} 
	 else
	 	num[x+half][y+half-1]=t;
	 	chess(x+half, y, x+half, y+half-1, half);
	}
}

int main(int argc,const char* argv[])
{
	int aa,bb,length;
	int i,j; 
	
	cin>>aa>>bb>>length;
	
	num[aa][bb]=0;
	
	chess(1,1,aa,bb,length);
	
	for(i=1;i<=length;i++)
	{
		for(j=1;j<=length;j++)
		{
			cout<<setw(4)<<num[i][j];
		}
		cout<<endl;
	}
	
	return 0;
 }


评论列表

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。