棋盘覆盖问题

问题说明

在一个2^k * 2^k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格。

棋盘覆盖问题就是要用图示的4种不同形态的L型骨牌覆盖给定棋盘上除特殊方格之外的所有方格，且任何2个L型骨牌不得重叠覆盖。

功能说明

本程序用分治法的思想解决了棋盘覆盖问题，显示输出

代码简述

用户输入数据，程序输入检测，动态分配空间，调用棋盘覆盖函数，把计算结果存储到board（二维数组指针），显示输出。

其中棋盘覆盖函数用分治的思想把棋盘分成四份，递归求解。

源码示例：

#include<iostream>#include<math.h>#include<cctype>usingnamespacestd;intnum_Now =0;//记录L型骨牌编号int**board =NULL;//棋盘指针//函数声明voidChessBoard(intnum_BoardTopLeftRow,intnum_BoardTopLeftColumn,intnum_SpecialRow,intnum_SpecialColumn,intboardSize);intmain() {intnum_BoardTopLeftRow =0,//棋盘左上角的行号num_BoardTopLeftColumn =0,//棋盘左上角的列号num_SpecialRow =0,//特殊方格所在的行号num_SpecialColumn =0,//特殊方格所在的列号boardSize =0,//棋盘大小k =0;//构成的(2^k)*(2^k)个方格的棋盘//用户界面cout <<"---------------- 棋盘覆盖问题 ----------------"<< endl;cout <<"请输入k(k>=0)，构成(2^k)*(2^k)个方格的棋盘"<< endl;//输入k值cin >> k;//判断输入数据合法性，包括检查输入是否为数字，k值是否大于0if(cin.fail() || k <0){cout <<"输入k错误！"<< endl;system("pause");return0;}//计算棋盘大小boardSize =pow(2, k);cout <<"请输入特殊方格所在的行号和列号（从0开始，用空格隔开）"<< endl;//输入特殊方格所在的行号和列号cin >> num_SpecialRow >> num_SpecialColumn;//判断输入数据合法性，包括检查输入是否为数字，特殊方格行号列号是否大于0，特殊方格行号列号是否不大于棋盘大小if(cin.fail() || num_SpecialRow <0|| num_SpecialColumn <0|| num_SpecialRow >= boardSize || num_SpecialColumn >= boardSize){cout <<"输入行号或列号错误！"<< endl;system("pause");return0;}//分配棋盘空间board =newint*[boardSize];for(autoi =0; i < boardSize; i++){board[i] =newint[boardSize];}//为特殊方格赋初值0board[num_SpecialRow][num_SpecialColumn] =0;//执行棋盘覆盖函数ChessBoard(num_BoardTopLeftRow, num_BoardTopLeftColumn, num_SpecialRow, num_SpecialColumn, boardSize);//显示输出cout <<"------------------------------------------------"<< endl;for(autoi =0; i < boardSize; i++){for(autoj =0; j < boardSize; j++){cout << board[i][j] <<"\t";}cout << endl;}cout <<"------------------------------------------------"<< endl;//暂停查看结果system("pause");//释放内存for(inti =0; i <= boardSize; i++)delete[]board[i];delete[]board;//指针置空board =NULL;return0;}//棋盘覆盖函数voidChessBoard(intnum_BoardTopLeftRow,intnum_BoardTopLeftColumn,intnum_SpecialRow,intnum_SpecialColumn,intboardSize){//棋盘大小为1则直接返回if(boardSize ==1)return;intnum = ++num_Now,//L型骨牌编号size = boardSize /2;//分割棋盘，行列各一分为二//覆盖左上角子棋盘if(num_SpecialRow < num_BoardTopLeftRow + size && num_SpecialColumn < num_BoardTopLeftColumn + size){//递归覆盖含有特殊方格的子棋盘ChessBoard(num_BoardTopLeftRow, num_BoardTopLeftColumn, num_SpecialRow, num_SpecialColumn, size);}else{//用编号为num的L型骨牌覆盖右下角board[num_BoardTopLeftRow + size -1][num_BoardTopLeftColumn + size -1] = num;//递归覆盖其余棋盘ChessBoard(num_BoardTopLeftRow, num_BoardTopLeftColumn, num_BoardTopLeftRow + size -1, num_BoardTopLeftColumn + size -1, size);}//覆盖右上角子棋盘if(num_SpecialRow < num_BoardTopLeftRow + size && num_SpecialColumn >= num_BoardTopLeftColumn + size){//递归覆盖含有特殊方格的子棋盘ChessBoard(num_BoardTopLeftRow, num_BoardTopLeftColumn + size, num_SpecialRow, num_SpecialColumn, size);}else{//用编号为num的L型骨牌覆盖左下角board[num_BoardTopLeftRow + size -1][num_BoardTopLeftColumn + size] = num;//递归覆盖其余棋盘ChessBoard(num_BoardTopLeftRow, num_BoardTopLeftColumn + size, num_BoardTopLeftRow + size -1, num_BoardTopLeftColumn + size, size);}//覆盖左下角子棋盘if(num_SpecialRow >= num_BoardTopLeftRow + size && num_SpecialColumn < num_BoardTopLeftColumn + size){//递归覆盖含有特殊方格的子棋盘ChessBoard(num_BoardTopLeftRow + size, num_BoardTopLeftColumn, num_SpecialRow, num_SpecialColumn, size);}else{//用编号为num的L型骨牌覆盖右上角board[num_BoardTopLeftRow + size][num_BoardTopLeftColumn + size -1] = num;//递归覆盖其余棋盘ChessBoard(num_BoardTopLeftRow + size, num_BoardTopLeftColumn, num_BoardTopLeftRow + size, num_BoardTopLeftColumn + size -1, size);}//覆盖右下角子棋盘if(num_SpecialRow >= num_BoardTopLeftRow + size && num_SpecialColumn >= num_BoardTopLeftColumn + size){//递归覆盖含有特殊方格的子棋盘ChessBoard(num_BoardTopLeftRow + size, num_BoardTopLeftColumn + size, num_SpecialRow, num_SpecialColumn, size);}else{//用编号为num的L型骨牌覆盖左上角board[num_BoardTopLeftRow + size][num_BoardTopLeftColumn + size] = num;//递归覆盖其余棋盘ChessBoard(num_BoardTopLeftRow + size, num_BoardTopLeftColumn + size, num_BoardTopLeftRow + size, num_BoardTopLeftColumn + size, size);}}

今天的分享就到这里了，大家要好好学C++哟~

写在最后：对于准备学习C/C++编程的小伙伴，如果你想更好的提升你的编程核心能力（内功）不妨从现在开始！

编程学习书籍分享：

编程学习视频分享：

整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）

欢迎转行和学习编程的伙伴，利用更多的资料学习成长比自己琢磨更快哦！

对于C/C++感兴趣可以关注小编在后台私信我：【编程交流】一起来学习哦！可以领取一些C/C++的项目学习视频资料哦！已经设置好了关键词自动回复，自动领取就好了！