草庐IT

棋盘覆盖问题——分治法

Oo名字不好取oO 2023-12-26 原文

问题描述

有一个 x （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 }

参考资料：《计算机算法设计与分析（第四版）》  

mdash棋盘spanstylecolor算法与数据结构

有关棋盘覆盖问题——分治法的更多相关文章

  1. ruby - 在 64 位 Snow Leopard 上使用 rvm、postgres 9.0、ruby 1.9.2-p136 安装 pg gem 时出现问题 - 2

    我想为Heroku构建一个Rails3应用程序。他们使用Postgres作为他们的数据库，所以我通过MacPorts安装了postgres9.0。现在我需要一个postgresgem并且共识是出于性能原因你想要pggem。但是我对我得到的错误感到非常困惑当我尝试在rvm下通过geminstall安装pg时。我已经非常明确地指定了所有postgres目录的位置可以找到但仍然无法完成安装:$envARCHFLAGS='-archx86_64'geminstallpg--\--with-pg-config=/opt/local/var/db/postgresql90/defaultdb/po

  2. ruby - 通过 rvm 升级 ruby​​gems 的问题 - 2

    尝试通过RVM将RubyGems升级到版本1.8.10并出现此错误:$rvmrubygemslatestRemovingoldRubygemsfiles...Installingrubygems-1.8.10forruby-1.9.2-p180...ERROR:Errorrunning'GEM_PATH="/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/ruby-1.9.2-p180@global:/Users/foo/.rvm/gems/ruby-1.9.2-p180:/Users/foo/.rvm/gems/rub

  3. ruby-on-rails - 在混合/模块中覆盖模型的属性访问器 - 2

    我有一个包含模块的模型。我想在模块中覆盖模型的访问器方法。例如:classBlah这显然行不通。有什么想法可以实现吗？ 最佳答案 您的代码看起来是正确的。我们正在毫无困难地使用这个确切的模式。如果我没记错的话，Rails使用#method_missing作为属性setter，因此您的模块将优先，阻止ActiveRecord的setter。如果您正在使用ActiveSupport::Concern(参见thisblogpost)，那么您的实例方法需要进入一个特殊的模块:classBlah

  4. ruby - 通过 RVM (OSX Mountain Lion) 安装 Ruby 2.0.0-p247 时遇到问题 - 2

    我的最终目标是安装当前版本的RubyonRails。我在OSXMountainLion上运行。到目前为止，这是我的过程:已安装的RVM$\curl-Lhttps://get.rvm.io|bash-sstable检查已知(我假设已批准)安装$rvmlistknown我看到当前的稳定版本可用[ruby-]2.0.0[-p247]输入命令安装$rvminstall2.0.0-p247注意:我也试过这些安装命令$rvminstallruby-2.0.0-p247$rvminstallruby=2.0.0-p247我很快就无处可去了。结果:$rvminstall2.0.0-p247Search

  5. ruby - Fast-stemmer 安装问题 - 2

    由于fast-stemmer的问题，我很难安装我想要的任何ruby​​gem。我把我得到的错误放在下面。Buildingnativeextensions.Thiscouldtakeawhile...ERROR:Errorinstallingfast-stemmer:ERROR:Failedtobuildgemnativeextension./System/Library/Frameworks/Ruby.framework/Versions/2.0/usr/bin/rubyextconf.rbcreatingMakefilemake"DESTDIR="cleanmake"DESTDIR=

  6. ruby - 无法覆盖 irb 中的 to_s - 2

    我在pry中定义了一个函数:to_s，但我无法调用它。这个方法去哪里了，怎么调用？pry(main)>defto_spry(main)*'hello'pry(main)*endpry(main)>to_s=>"main"我的ruby版本是2.1.2看了一些答案和搜索后，我认为我得到了正确的答案:这个方法用在什么地方？在irb或pry中定义方法时，会转到Object.instance_methods[1]pry(main)>defto_s[1]pry(main)*'hello'[1]pry(main)*end=>:to_s[2]pry(main)>defhello[2]pry(main)

  7. ruby - 安装 Ruby 时遇到问题(无法下载资源 "readline--patch") - 2

    当我尝试安装Ruby时遇到此错误。我试过查看this和this但无济于事➜~brewinstallrubyWarning:YouareusingOSX10.12.Wedonotprovidesupportforthispre-releaseversion.Youmayencounterbuildfailuresorotherbreakages.Pleasecreatepull-requestsinsteadoffilingissues.==>Installingdependenciesforruby:readline,libyaml,makedepend==>Installingrub

  8. ruby - 覆盖相似的方法，更短的语法 - 2

    在Ruby类中，我重写了三个方法，并且在每个方法中，我基本上做同样的事情:classExampleClassdefconfirmation_required?is_allowed&&superenddefpostpone_email_change?is_allowed&&superenddefreconfirmation_required?is_allowed&&superendend有更简洁的语法吗？如何缩短代码？ 最佳答案 如何使用别名？classExampleClassdefconfirmation_required?is_a

  9. ruby - 是否可以覆盖 gemfile 进行本地开发？ - 2

    我们的git存储库中目前有一个Gemfile。但是，有一个gem我只在我的环境中本地使用(我的团队不使用它)。为了使用它，我必须将它添加到我们的Gemfile中，但每次我checkout到我们的master/dev主分支时，由于与跟踪的gemfile冲突，我必须删除它。我想要的是类似Gemfile.local的东西，它将继承从Gemfile导入的gems，但也允许在那里导入新的gems以供使用只有我的机器。此文件将在.gitignore中被忽略。这可能吗？ 最佳答案 设置BUNDLE_GEMFILE环境变量:BUNDLE_GEMFI

  10. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

随机推荐