Go语言视频零基础入门到精通

javalearner

在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何
k≥0,有4^k种不同的特殊棋盘.
下图中的特殊棋盘是当k=2时中的一种

棋盘中的特殊方格如图


   使用以下四种L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖.如何覆盖？


   
  
   
   
     
   

     
   
  
思路分析：
当k>0时,将2^k×2^k棋盘分割为4个2^k－1×2^k－1子棋盘,如下图�图(3)所示：


    特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格.为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处。

如下图所示,这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而原问题转化为4个较小规模的棋盘覆盖问题.递归地使用这种分割,直至棋盘简化为1×1棋盘。



（1）特殊方格在左上区域，那么其他几个区域的特殊方格可定，用如下一个L型骨牌覆盖3个无特殊方格的子棋盘会合处。

（2）特殊方格在右上区域，那么其他几个区域的特殊方格可定，用如下一个L型骨牌覆盖3个无特殊方格的子棋盘会合处。


（3）特殊方格在左下区域，那么其他几个区域的特殊方格可定，用如下一个L型骨牌覆盖3个无特殊方格的子棋盘会合处。

（4）特殊方格在右下区域，那么其他几个区域的特殊方格可定，用如下一个L型骨牌覆盖3个无特殊方格的子棋盘会合处。

java 代码：

1. import java.util.Scanner;
   
2. public class chessBoard
   
3. {   
   
4. private  int dr,dc,size; // dr: 特殊方格的排号。dc: 特殊方格的列号。size:棋盘规格
   
5. private  int[][]board;
   
6. 
   
7. public chessBoard(int size,int dc,int dr){
   
8.   this.size=size;
   
9.   this.dc=dc;
   
10.   this.dr=dr;
    
11.   board=new int[this.size][this.size];
    
12.   init();
    
13. }
    
14. 
    
15. private void init() {
    
16.   for(int i=0;i< size;i++)
    
17.    for(int j=0;j< size;j++) board[i][j]=0;
    
18. }
    
19. 
    
20. public void chessBoard(int tr,int tc,int dr,int dc,int size){
    
21.   if(size==1) return;
    
22.   int s=size/2;
    
23.      //特殊方格在左上角
    
24.   if(dr< tr+s && dc< tc+s){//覆盖第四个L型骨牌
    
25.    board[tr+s-1][tc+s]=4; //右上
    
26.    board[tr+s][tc+s-1]=4;//左下
    
27.    board[tr+s][tc+s]=4;//右下
    
28.    chessBoard(tr,tc,dr,dc,s);//左上
    
29.    chessBoard(tr,tc+s,tr+s-1,tc+s,s);//右上
    
30.    chessBoard(tr+s,tc,tr+s,tc+s-1,s);//左下
    
31.    chessBoard(tr+s,tc+s,tr+s,tc+s,s);//右下
    
32.   }
    
33.      //特殊方格在右上角
    
34.   if(dr< tr+s && dc>=tc+s){//覆盖第3个L型骨牌
    
35.    board[tr+s-1][tc+s-1]=3; //左上
    
36.    board[tr+s][tc+s-1]=3;//左下
    
37.    board[tr+s][tc+s]=3;//右下
    
38.    chessBoard(tr,tc,tr+s-1,tc+s-1,s);//左上
    
39.    chessBoard(tr,tc+s,dr,dc,s);   //右上
    
40.    chessBoard(tr+s,tc,tr+s,tc+s-1,s);//左下
    
41.    chessBoard(tr+s,tc+s,tr+s,tc+s,s);//右下
    
42.   }
    
43.      //特殊方格在左下角
    
44.   if(dr>=tr+s && dc< tc+s){//覆盖第2个L型骨牌
    
45.    board[tr+s-1][tc+s-1]=2; //左上
    
46.    board[tr+s-1][tc+s]=2;//右上
    
47.    board[tr+s][tc+s]=2;//右下
    
48.    chessBoard(tr,tc,tr+s-1,tc+s-1,s);//左上
    
49.    chessBoard(tr,tc+s,tr+s-1,tc+s,s);//右上
    
50.    chessBoard(tr+s,tc,dr,dc,s);//左下
    
51.    chessBoard(tr+s,tc+s,tr+s,tc+s,s);//右下
    
52.    }
    
53.      //特殊方格在右下角
    
54.   if(dr>=tr+s && dc>=tc+s){//覆盖第1个L型骨牌
    
55.    board[tr+s-1][tc+s-1]=1; //左上
    
56.    board[tr+s-1][tc+s]=1;//右上
    
57.    board[tr+s][tc+s-1]=1;//左下
    
58.    chessBoard(tr,tc,tr+s-1,tc+s-1,s);//左上
    
59.    chessBoard(tr,tc+s,tr+s-1,tc+s,s);//右上
    
60.    chessBoard(tr+s,tc,tr+s,tc+s-1,s);//左下
    
61.    chessBoard(tr+s,tc+s,dr,dc,s);//右下
    
62.   }
    
63. }
    
64. 
    
65. public void showChess(){
    
66.   for (int i = 0; i < size; i++) {
    
67.    for (int j = 0; j < size; j++)
    
68.    { System.out.print(board[i][j]+" ");}
    
69.    System.out.println();       }
    
70. }
    
71. 
    
72. public static void main(String[] args) {
    
73.   int size,dr,dc;
    
74.         System.out.println("请输入棋盘的边长 ");
    
75.         Scanner reader= new Scanner(System.in);
    
76.   size=reader.nextInt(); //边长(4的倍数)
    
77.   System.out.println("请输入棋盘特殊方格的具体位置(排号    列号)：");
    
78.   dr=reader.nextInt()-1; //排号
    
79.   dc=reader.nextInt()-1; //列号
    
80.   chessBoard chess=new chessBoard(size,dr,dc);
    
81.   chess.chessBoard(0, 0, dr, dc, size);
    
82.   chess.showChess();}
    
83. }

复制代码

运行结果：


另有图形界面的程序（请下载）




  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/30/000653000.zip