棋盘覆盖问题——分治法

问题描述

有一个 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日

相关文章

  • Java数据结构之实现跳表

    Java数据结构之实现跳表,是一篇对跳表数据结构的详细讲解。 背景 跳表是一种基于有序链表的高效查找算法,它的查找时间复杂度为O(logn),相比于普通链表的O(n),具有很大的优势。本文将介绍跳表的实现过程。 实现跳表 1. 跳表结构体 跳表的数据结构体实现包含以下四项: 头结点head:表示链表的起始位置。 节点Node:跳表中的节点,包含表层链表和下层…

    数据结构 2023年5月17日
    00
  • Python PSO算法处理TSP问题详解

    以下是关于“Python PSO算法处理TSP问题详解”的完整攻略: 简介 TSP问题(Traveling Salesman Problem)是一种经典的组合优化问题,它的目标是在给定的一组城市和它们之间的距离矩阵中,找到一条最短的路径,使得每个城市恰好被访问一次,最后回到起点。在教程中,我们将介绍如何使用Python实现PSO算法来解决TSP问题,并使用可…

    python 2023年5月14日
    00
  • C语言数据结构与算法之排序总结(二)

    C语言数据结构与算法之排序总结(二) 本篇文章是关于C语言数据结构与算法中排序算法的详细讲解,涉及了八种排序算法。 冒泡排序(Bubble Sort) 冒泡排序是一种简单的排序算法。在排序过程中,它会重复地交换相邻的元素,这是它名称的由来。 示例代码: c void bubble_sort(int arr[], int n) { for (int i = 0…

    数据结构 2023年5月17日
    00
  • C语言数据结构实现银行模拟

    C语言数据结构实现银行模拟攻略 背景介绍 银行模拟是计算机学科中一个重要的数据结构实践练习项目。它涉及到队列(Queue)等数据结构的应用,也是计算机基础课程的一个重要组成部分。 代码实现 1. 队列的实现 首先,我们需要实现一个队列(Queue)结构体,包含 QueueSize、Front、Rear 三个成员变量: struct Queue { int Q…

    数据结构 2023年5月17日
    00
  • 解析从源码分析常见的基于Array的数据结构动态扩容机制的详解

    解析从源码分析常见的基于Array的数据结构动态扩容机制的详解 什么是动态扩容机制 动态扩容机制是指,当一个数据结构达到其容量限制时,自动增加容量大小以继续存储新的数据。在动态扩容时,需要考虑到时间和空间的平衡,因为扩容需要分配新的内存空间,在处理大量数据时,需要尽可能减少空间浪费和分配内存的时间消耗。 基于Array的数据结构 Array是一种连续存储的数…

    数据结构 2023年5月17日
    00
  • 使用python实现ANN

    以下是关于“使用Python实现ANN”的完整攻略: 简介 人工神经网络(Artificial Neural Network,ANN)是一种模拟人脑神经元之间相互作用的计算模型,它可以用于分类、回归和聚类等任务。在本教程中,我们将介绍如何使用Python实现ANN,并提供两个示例说明。 实现ANN 以下是使用Python实现ANN的代码: import nu…

    python 2023年5月14日
    00
  • C++数据结构深入探究栈与队列

    C++数据结构深入探究栈与队列 简介 栈和队列是常见的数据结构,尤其在程序设计和算法中都是不可或缺的。本文将深入讲解C++中栈和队列的实现原理和基本操作,并提供两个示例说明其应用。 栈(Stack)基本操作 栈的定义 栈是一种线性数据结构,具有后进先出(Last In First Out, LIFO)的特点。栈可以用数组或链表实现。 栈的操作 push() …

    数据结构 2023年5月17日
    00
  • mysql的Buffer Pool存储及原理解析

    下面我就来详细讲解一下“mysql的Buffer Pool存储及原理解析”的攻略。 Buffer Pool简介 在MySQL中,Buffer Pool是一个重要的概念,也可以说是MySQL最重要的性能优化建议之一。Buffer Pool是MySQL内存中缓存数据页的数据结构,用于加速数据的读写。 数据页 在MySQL中,数据是以数据页(page)为单位进行读…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部