分治法之棋盘覆盖

棋盘覆盖

1.问题描述

分治法之棋盘覆盖分治法之棋盘覆盖
4k为总的方格数, 1为特殊方格, 每个L型骨牌有3个方格,所以除以3。

2.问题分析

对于2k*2k的棋盘有以下特点

  1. 棋盘为正方形,则可以考虑将问题分为规模相等的子问题、
  2. 棋盘上有一个残缺的方格,则分解后的子问题中也应该有一个残缺的方格

分治法之棋盘覆盖

3.分治算法

分治法之棋盘覆盖
分治法之棋盘覆盖

4 时间复杂性

分治法之棋盘覆盖

分治法之棋盘覆盖

5 代码

#include <iostream>
using namespace std;
# define N 1024
int board[N][N];
int title=1;
//(tr,tc)表示棋盘的起始位置 
//(dr,dc)表示残缺方块的位置
//size=2^k,棋盘规模为 2^k*2^k
void chessBoard(int tr, int tc, int dr, int dc, int size)
   {
      if (size == 1) return;
      int t = title++, // L型骨牌号
       s = size/2;  // 分割棋盘
      // 覆盖左上角子棋盘
      if (dr < tr + s && dc < tc + s)
         // 特殊方格在此棋盘中
         chessBoard(tr, tc, dr, dc, s);
      else {// 此棋盘中无特殊方格
         // 用 t 号L型骨牌覆盖右下角
         board[tr + s - 1][tc + s - 1] = t;
         // 覆盖其余方格
         chessBoard(tr, tc, tr+s-1, tc+s-1, s);}
      // 覆盖右上角子棋盘
      if (dr < tr + s && dc >= tc + s)
         // 特殊方格在此棋盘中
         chessBoard(tr, tc+s, dr, dc, s);
      else {// 此棋盘中无特殊方格
         // 用 t 号L型骨牌覆盖左下角
	  board[tr + s - 1][tc + s] = t;
         // 覆盖其余方格
         chessBoard(tr, tc+s, tr+s-1, tc+s, s);}
	  // 覆盖右下角子棋盘
      if (dr >= tr + s && dc >= tc + s)
         // 特殊方格在此棋盘中
         chessBoard(tr+s, tc+s, dr, dc, s);
      else {// 用 t 号L型骨牌覆盖左上角
         board[tr+s][tc+s] = t;
         // 覆盖其余方格
         chessBoard(tr+s,tc+s,tr+s,tc+s,s);}
        // 覆盖左下角子棋盘
      if (dr >= tr + s && dc < tc + s)
         // 特殊方格在此棋盘中
         chessBoard(tr+s, tc, dr, dc, s);
      else {// 用 t 号L型骨牌覆盖右上角
         board[tr + s][tc + s - 1] = t;
         // 覆盖其余方格
         chessBoard(tr+s, tc, tr+s, tc+s-1, s);}
      
   }

	

int main()
{
	int aa,bb,length;
	scanf("%d%d%d",&aa,&bb,&length);
	for(int i=0;i<length;i++)
		for(int j=0;j<length;j++)
		{
			board[i][j]=0;
		}
	chessBoard(0,0,aa-1,bb-1,length);
	for(int i=0;i<length;i++)
	{
		for(int j=0;j<length;j++)
		{
			printf("%4d",board[i][j]);
           
		}
		printf("\n");
	}
	return 0;
}


运行截图
分治法之棋盘覆盖

上一篇:GoLang 数据结构(稀疏数组)


下一篇:小游戏二之---------------五子棋