棋盘覆盖问题——分治法

问题描述

有一个 2^kx2^k (k>0)的棋盘,恰好有一个方格与其他方格不同,称之为特殊方格。现在要用如下图所示的L形骨牌覆盖除了特殊方格以外的其他全部方格,骨牌可以任意旋转,并且任何两个骨牌不能重复。请给出一种覆盖方式。

棋盘覆盖问题——分治法

 

样例:

输入:

棋盘覆盖问题——分治法

输出:

棋盘覆盖问题——分治法

 

思路——分治法:

将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。

递归地解决这些子问题,然后将各个子问题的解合并得到原问题的解。

就是将规模为n的问题自顶向下分解,直到小问题分解到足够小,可以解决时,再自底向上合并,从而得到原来的解。

 

当k=0(棋盘只有1格),特殊点只能唯一,L骨牌数为0

当k >0,则可将 2*kⅹ2*k 棋盘分割为 4个 2*k-1ⅹ2*k-1 的子棋盘

棋盘覆盖问题——分治法

判断特殊点在哪一个子棋盘中,用一块L骨牌放在其它三个子棋盘的连接处

以此类推,则最后可将每个子棋盘划分为1格的棋盘,结束递归

 

代码实现:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int arr[1000][1000];
 7 int num = 0;
 8 void ChessBoard(int x, int y, int a, int b, int length);
 9 
10 int main() {
11     //棋盘大小
12     int length;
13     cout << "请输入length:" ;
14     cin >> length;
15 
16     //空白点坐标
17     int a, b;
18     cout << "请输入空格位置:";
19     cin >> a >> b;
20     cout << endl;
21 
22     arr[a][b] = 0;//标点用0表示
23     ChessBoard(1, 1, a, b, length);
24     for (int i = 1; i <= length; i++) {
25         for (int j = 1; j <= length; j++) {
26             cout << arr[i][j] << "   ";
27         }
28         cout << endl;
29     }
30     return 0;
31 }
32 
33 void ChessBoard(int x, int y, int a, int b, int length) {
34     if (length == 1) {
35         return;
36     }
37     int h = length / 2;//分割棋盘
38     int t = ++num;//骨牌号,从1开始,相同数字代表是同一块
39 
40     //以“田”的左下角为(1,1)
41     //左下角
42     if (a < x + h && b < y + h) {
43         ChessBoard(x, y, a, b, h);
44     }
45     else {
46         arr[x + h - 1][y + h - 1] = t;
47         ChessBoard(x, y, x + h - 1, y + h - 1, h);
48     }
49 
50     //左上角
51     if (a < x + h && b >= y + h) {
52         ChessBoard(x, y + h, a, b, h);
53     }
54     else {
55         arr[x + h - 1][y + h] = t;
56         ChessBoard(x, y + h, x + h - 1, y + h, h);
57     }
58 
59     //右下角
60     if (a >= x + h && b < y + h) {
61         ChessBoard(x + h, y, a, b, h);
62     }
63     else {
64         arr[x + h][y + h - 1] = t;
65         ChessBoard(x + h, y, x + h, y + h - 1, h);
66     }
67 
68     //右上角
69     if (a >= x + h && b >= y + h) {
70         ChessBoard(x + h, y + h, a, b, h);
71     }
72     else {
73         arr[x + h][y + h] = t;
74         ChessBoard(x + h, y + h, x + h, y + h, h);
75     }
76 }

参考资料:《计算机算法设计与分析(第四版)》  

原文链接:https://www.cnblogs.com/RyunosukeAkasaka/p/17354348.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:棋盘覆盖问题——分治法 - Python技术站

(0)
上一篇 2023年4月25日
下一篇 2023年4月30日

相关文章

  • Python排序算法之冒泡排序

    Python排序算法之冒泡排序 冒泡排序是一种简单的排序算法,它重复地遍历要排序的列表,比较相邻两个元素,如果它们的顺序错误就交换它们的位置。通过多次遍历,最大的元素逐渐“冒泡”到列表的末尾,从而实现排序。在本攻略中,我们将介绍如何使用Python实现冒泡排序法。 步骤1:实现冒泡排序算法 在使用Python实现冒泡排序算法之前,我们需要先了解冒泡排序的基本…

    python 2023年5月14日
    00
  • C语言数据结构二叉树简单应用

    C语言数据结构二叉树简单应用攻略 1. 什么是二叉树? 二叉树(Binary Tree)是一种树形结构,它的每个节点最多包含两个子节点,它是非线性数据结构,可以用来表示许多问题,例如家族关系、计算机文件系统等等。 2. 二叉树的基本操作 二叉树的基本操作包括插入、删除、查找等等,本攻略主要讲解插入和查找的实现。 插入操作的代码如下: // 二叉树的插入操作 …

    数据结构 2023年5月17日
    00
  • C语言数据结构算法基础之循环队列示例

    标题:C语言数据结构算法基础之循环队列示例 1. 简介 循环队列是一种常见的数据结构,它采用固定大小的数组来模拟队列的数据结构,可以高效地处理队列的进出操作。本文将会讲解循环队列的实现原理和示例代码。 2. 循环队列基本原理 循环队列通过两个指针front和rear来实现队列的添加和删除操作。在初始化时,front和rear的初始值都为0。每当数据进入队列时…

    数据结构 2023年5月17日
    00
  • Oracle 11g Release (11.1) 索引底层的数据结构

    我来为您详细讲解“Oracle 11g Release (11.1) 索引底层的数据结构”的完整攻略。 索引底层数据结构简介 在Oracle数据库中,索引底层数据结构是B树(B-Tree)。B树是一种常用的多路平衡查找树,它的特点是每个节点都有多个子节点,能够自动调整高度,保持所有叶子节点到根节点的距离相等。在B树中,每个节点都有一个关键字列表和一个指向子节…

    数据结构 2023年5月17日
    00
  • C语言数据结构之队列算法详解

    C语言数据结构之队列算法详解 什么是队列? 在计算机科学中,队列是一种抽象数据类型或线性数据结构。它具有先进先出(FIFO)的特性,即先进入队列的元素先被处理或先被移除。队列通常用于解决先到先服务的问题(如请求处理),但也常用于广泛的异步编程中。 队列的特点 队列通常具有以下特点: 队列可以为空; 队列从队首插入元素,从队尾移除元素; 队列只允许从队尾插入元…

    数据结构 2023年5月17日
    00
  • 10个Python实现的最频繁使用的聚类算法

    10个Python实现的最频繁使用的聚类算法 聚类算法是一种无监督学习算法,它将数据集中对象分成不同的组或簇,使得同一组内的对象相似度较高,同组之间的对象相似度较低。Python中有许多聚类算法的实现,本文将详细讲解10个Python实现最频繁使用的聚类算法的完整攻略,包括算法原理、Python实现过程和示例说明。 1. K-Means算法 K-Means算…

    python 2023年5月13日
    00
  • C#数据结构与算法揭秘三 链表

    作为一本通俗易懂的C#数据结构与算法书籍,其第三章主要介绍链表(Linked List)的概念和基本操作。下面是链表的基本概念: 链表(Linked List)是一种动态数据结构,其中的元素按线性顺序排列,并且每个元素都称为一个结点(Node)。 每个结点都包含一个元素和一个指向下一个结点的指针(Pointer)。 相比于数组,链表的优势在于能够轻松地增加或…

    数据结构 2023年5月17日
    00
  • Python实现的数据结构与算法之快速排序详解

    下面是关于“Python实现的数据结构与算法之快速排序详解”的完整攻略。 1. 快速排序算法概述 快速排序是一种高效的排序算法,它的基本思想是通过分治的想将一个大问题解成多个小问题,后递归地解决这些小问题。快速排序的复杂度为O(nlogn),是一种非高的排序算法。 2 快速排序算法实现 下面使用Python实现快速排序的代码: def quick_sort(…

    python 2023年5月13日
    00
合作推广
合作推广
分享本页
返回顶部