java 实现棋盘覆盖问题

  • 问题描述:在一个2k*2k的棋盘中,有一个特殊方格,要求用L型骨牌覆盖满除特殊方格外的所有其他方格,且骨牌不得重叠.(骨牌可以旋转放置)
  • 输入:棋盘的边长、特殊方格坐标
  • 输出:骨牌放法.其中用0表示特殊方格,同一张骨牌所占方格用同一个数字表示,不同骨牌用不同数字.

 解题思想:

采用分治法解决该问题。分治法是把一个规模很大的问题分解为多个规模较小、类似的子问题,然后递归地解决所有子问题,最后再由子问题的解决得到原问题的解决。

所以将2k*2k的棋盘,先分成相等的四块子棋盘,其中特殊方格位于四个中的一个,构造剩下没特殊方格三个子棋盘:将一块骨牌放在这三个小棋盘的交界处,使骨牌的每一个方格都作为三个小棋盘的特殊方格,骨牌具体放法如下:

  • 左上的子棋盘若不存在特殊方格,将该子棋盘右下角的那个方格覆盖为特殊方格
  • 右上的子棋盘若不存在特殊方格,将该子棋盘左下角的那个方格覆盖为特殊方格
  • 左下的子棋盘若不存在特殊方格,将该子棋盘右上角的那个方格覆盖为特殊方格
  • 右下的子棋盘若不存在特殊方格,将该子棋盘左上角的那个方格覆盖为特殊方格 至此,每个小棋盘都有一个特殊方格,然后递归调用,就可以解决问题了。
public class Chess {
 
 /**  棋盘的规格  */
 public static int SIZE = 8;
 /**  特殊格子的竖坐标(从零开始)  */
 public static int TR = 1;
 /**  特殊格子的横坐标(从零开始)  */
 public static int TC = 1;

 /** 模拟棋盘  */
 static int[][] board;
 /** 模拟骨牌(相同数字为同一块骨牌)  */
 static int tile = 1;

 /**
  * 棋盘覆盖问题
  * @param dr  左上角方格行号
  * @param dc  左上角方格列号
  * @param tr  特殊方格行号
  * @param tc  特殊方格列号
  * @param size  2的正整数次方
  */
 public static void chessBoard(int dr, int dc, int tr, int tc, int size) {

  if (size == 1) {
   return;
  }

  int t = tile++; 
  /**  分割棋盘后的size  */
  int s = size / 2;

  // 判断特殊方格是否在左上角的小棋盘中
  if (tr < dr + s && tc < dc + s) {
   chessBoard(dr, dc, tr, tc, s);
  } else {
   board[dr + s - 1][dc + s - 1] = t;
   chessBoard(dr, dc, dr + s - 1, dc + s - 1, s);
  }

  // 判断特殊方格是否在右上角的小棋盘中
  if (tr < dr + s && tc >= dc + s) {
   chessBoard(dr, dc + s, tr, tc, s);
  } else {
   board[dr + s - 1][dc + s] = t;
   chessBoard(dr, dc + s, dr + s - 1, dc + s, s);
  }

  // 判断特殊方格是否在左下角的小棋盘中
  if (tr >= dr + s && tc < dc + s) {
   chessBoard(dr + s, dc, tr, tc, s);
  } else {
   board[dr + s][dc + s - 1] = t;
   chessBoard(dr + s, dc, dr + s, dc + s - 1, s);
  }

  // 判断特殊方格是否在youxia角的小棋盘中
  if (tr >= dr + s && tc >= dc + s) {
   chessBoard(dr + s, dc + s, tr, tc, s);
  } else {
   board[dr + s][dc + s] = t;
   chessBoard(dr + s, dc + s, dr + s, dc + s, s);
  }
 }

 public static void main(String[] args) {
  
  // init parameter
  try{
   if(args[0]!=null){
    SIZE = Integer.parseInt(args[0], 10);
   }
   if(args[1]!=null){
    TR = Integer.parseInt(args[1], 10);
   }
   if(args[2]!=null){
    TC = Integer.parseInt(args[2], 10);
   }
  }catch(Exception e){
   System.out.print("\t(部分)采用默认参数");
  }
  
  System.out.printf("\t棋盘规模:%d*%d",SIZE,SIZE);
  System.out.printf("\t特殊方格:(%d,%d)",TR,TC);
  
  // 初始化棋盘
  board = new int[SIZE][SIZE];
  // 调用方法进行测试
  chessBoard(0, 0, TR, TC, SIZE);
  // 显示棋盘结果
  for (int[] is : board) {
   System.out.println();
   for (int i : is) {
    System.out.printf("%4d", i);
   }
  }
 }
}

效果截图:

算法复杂性分析:

设T(k)是此算法所需的时间,则根据分治法可知:

解此递归方程可得,T(k)=O(4k)。由于覆盖2k*2k的棋盘所需的骨牌个数为(4k-1)/3,所以此算法是一个渐进意义下最优算法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习计算机视觉

一万副扑克分牌问题

问题描述:给你一万副扑克(一共540000张乱序)和一万个人,请设计一种算法,能够有效的将一万副扑克都分出来,并且每一副牌都是按数字和花色排好序的。 总任务:将...

2774
来自专栏程序人生

[技术] 谈谈编程思想

这段时间又攒了很多答应了,但还未动手的文章。大概一两周前,有个读者留言:「程序君,能发篇文章有关编程思想的吗?我是编程初学者,对编程思想没啥概念,求传授点经验!...

3416
来自专栏人工智能LeadAI

TensorFlow从1到2 | 第五章 非专家莫入!TensorFlow实现CNN

当看到本篇时,根据TensorFlow官方标准《Deep MNIST for Experts》(https://tensorflow.google.cn/get...

3708
来自专栏我的小碗汤

使用pprof优化golang性能

Donald E.Knuth说过一句非常著名的话,过早的优化是万恶之源。原文如下:

864
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

图像处理中任意核卷积(matlab中conv2函数)的快速实现。

     卷积其实是图像处理中最基本的操作,我们常见的一些算法比如:均值模糊、高斯模糊、锐化、Sobel、拉普拉斯、prewitt边缘检测等等一些和领域相关的算...

3408
来自专栏机器学习算法与Python学习

TensorFlow实战:SoftMax手写体MNIST识别(Python完整源码)

之前的文章 TensorFlow的安装与初步了解,从TensorFlow的安装到基本的模块单元进行了初步的讲解。今天这篇文章我们使用TensorFlow针对于手...

5826
来自专栏程序员互动联盟

【答疑释惑第四十三讲】到底什么是可执行文件?

疑惑一 到底什么是可执行文件? 可执行文件由一系列段(section)组成,text段用于存储代码,data段存储变量等数据,bss段用于存储未初始化的数据,比...

2876
来自专栏最高权限比特流

漫谈计算机组成原理(一)程序是怎么跑起来的

我们知道,计算机是由软件和硬件共同组成的。没有硬件,软件就没有用武之地;没有软件,硬件就只能是一堆废铁。 而软件又分为两类:

2084
来自专栏Java呓语

策略模式(分离算法,选择实现)

如果您是第一次阅读我的设计模式系列文章,建议先阅读设计模式开篇,希望能得到您宝贵的建议。

793
来自专栏程序员的诗和远方

20180708_ARTS_week02

Add Two Numbers You are given two non-empty linked lists representing two non-ne...

591

扫描关注云+社区