棋盘覆盖问题就是一个很经典的分治问题
首先我们先来看一下棋盘覆盖问题到底是个什么问题?
代码C语言实现:
#include<stdio.h> #define max 1024 int cb[max][max];//最大棋盘 int id=0;//覆盖标志位 int chessboard(int tr,int tc,int dr,int dc,int size)//tr,tc代表棋盘左上角的位置,dr ,dc代表棋盘不可覆盖点的位置,size是棋盘大小 { if(size==1)//如果递归到某个时候,棋盘大小为1,则结束递归 { return 0; } int s=size/2;//使得新得到的棋盘为原来棋盘大小的四分之一 int t=id++; if(dr<tr+s&&dc<tc+s)//如果不可覆盖点在左上角,就对这个棋盘左上角的四分之一重新进行棋盘覆盖 { chessboard(tr,tc,dr,dc,s); }else//因为不可覆盖点不在左上角,所以我们要在左上角构造一个不可覆盖点 { cb[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//因为不可覆盖点不在右上角,所以我们要在右上角构造一个不可覆盖点 { cb[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,dr,dc,s); }else//因为不可覆盖点不在左下角,所以我们要在左下角构造一个不可覆盖点 { cb[tr+s][tc+s-1]=t; chessboard(tr+s,tc,tr+s,tc+s-1,s);//在我们构造完不可覆盖点之后,棋盘的左下角的四分之一又有了不可覆盖点,所以就对左下角棋盘的四分之一进行棋盘覆盖 } if(dr>=tr+s&&dc>=tc+s)//如果不可覆盖点在右下角,就对这个棋盘右下角的四分之一重新进行棋盘覆盖 { chessboard(tr+s,tc+s,dr,dc,s); }else//因为不可覆盖点不在右下角,所以我们要在右下角构造一个不可覆盖点 { cb[tr+s][tc+s]=t; chessboard(tr+s,tc+s,tr+s,tc+s,s);//在我们构造完不可覆盖点之后,棋盘的右下角的四分之一又有了不可覆盖点,所以就对右下角棋盘的四分之一进行棋盘覆盖 } //后面的四个步骤都跟第一个类似 } int main() { printf("请输入正方形棋盘的大小(行数):\n"); int n; scanf("%d",&n); printf("请输入在%d*%d棋盘上不可覆盖点的位置:\n",n,n); int i,j,k,l; scanf("%d %d",&i,&j); printf("不可覆盖点位置输入完毕,不可覆盖点的值为-1\n"); cb[i][j]=-1; chessboard(0,0,i,j,n); for(k=0;k<n;k++) { printf("%2d",cb[k][0]); for(l=1;l<n;l++) { printf(" %2d",cb[k][l]); } printf("\n"); } return 0; }
运行结果如下:
当棋盘大小为4,且特殊方格在第一行第一列时
当棋盘大小为4,且特殊方格在第一行第二列时
当棋盘大小为8,且特殊方格在第二行第三列时
参考:https://blog.csdn.net/acm_jl/article/details/50938164
https://www.cnblogs.com/yinbiao/p/8666209.html