欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

棋盘覆盖问题

程序员文章站 2022-06-03 17:00:15
...

棋盘覆盖问题

题目

在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。

思想

利用分治法的思想,主要通过递归来实现。将棋盘分为大小相等的四部分,进行处理,一直到棋盘大小为1结束。
初始时,将棋盘分为大小相等的四部分之后,一定有亿部分中含有特殊方格,因此就可以从其他三部分中各取出一块组成L型骨牌,如图
棋盘覆盖问题
蓝色的起特殊方格,绿色的为L型骨牌,将放置L型骨牌的地方也当作特殊方格,那没就可以将原问题分解为四个与原问题相同且相互独立的子问题,在分别处理这四个子问题,处理方法同上,因此可以通过递归实现
具体见代码

代码

#include<bits/stdc++.h>

using namespace std;

int cnt=0;//作为全局变量,记录L型骨牌的编号
int board[100][100];//棋盘

//tr:当前棋盘中左上角的行号
//tc:当前棋盘中左上角的列号
//x:当前棋盘中特殊标记所在位置行号
//y:当前期盼中特殊标记所在位置列号
//size:当前棋盘的大小
void ChessBoard(int tr,int tc,int x,int y,int size)
{
    if(size==1)
        return ;//相当于递归结束的条件
    int t=++cnt;//当前要添加的L型骨牌编号
    int s=size/2;//棋盘中间的行号和列号(因为行数等于列数,所以棋盘中间行号列号相等)
    if(x<tr+s&&y<tc+s)//如果特殊方格在左上角的那四分之一部分内
    {
        ChessBoard(tr,tc,x,y,s);//说明此时不用放置L型骨牌,继续递归处理这四分之一棋盘
    }
    else//若这四分之一中没有特殊方格
    {
        board[tr+s-1][tc+s-1]=t;//这四分之一方格的最右下角作为L型骨牌的一部分
        ChessBoard(tr,tc,tr+s-1,tc+s-1,s);//继续递归处理这四分之一棋盘
    }
    if(x<tr+s&&y>=tc+s)//操作原理同处理右上角那四分之一
    {
        ChessBoard(tr,tc+s,x,y,s);//这里是右上角那四分之一,所以此时的行号为tr,列号为tc+s
    }
    else
    {
        board[tr+s-1][tc+s]=t;
        ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
    }
    if(x>=tr+s&&y<tc+s)
    {
        ChessBoard(tr+s,tc,x,y,s);
    }
    else
    {
        board[tr+s][tc+s-1]=t;
        ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
    }
    if(x>=tr+s&&y>=tc+s)
    {
        ChessBoard(tr+s,tc+s,x,y,s);
    }
    else
    {
        board[tr+s][tc+s]=t;
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
    }
    return ;
}

int main()
{
    int size;//方格的大小
    int u,v;//记录特殊方格的位置
    cin>>size;
    cin>>u>>v;
    ChessBoard(0,0,u,v,size);
    for(int i=0;i<size;i++)
    {
        for(int j=0;j<size;j++)
        {
            cout<<board[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}