java实现的棋盘覆盖

　　

　　课课家和大家分享一些Java实现的棋盘覆盖的思路：应用分治法 

　　分治的技巧在于如何划分棋盘，使划分后的子棋盘的大小相同，并且每个子棋盘均包含一个特殊方格，从而将原问题分解为规模较小的棋盘覆盖问题。k>0 时，可将2^k×2^k的棋盘划分为4个2^(k-1)×2^(k-1)的子棋盘。这样划分后，由于原棋盘只有一个特殊方格，所 以，这4个子棋盘中只有一个子棋盘包含该特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化为特殊棋盘，以便采用递归方法求 解，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略， 直至将棋盘分割为1×1的子棋盘。 

　　递归：在一个算法调用另一个算法时，系统需要建立递归调用工作栈，并在运行被调用算法之前先完成3件事： 

　　(1)将所有的实参参数，返回地址等信息传递给被调算法保存。

　　(2)为被调算法的局部变量分配存储区。 

　　(3)将控制转移到被调函数的入口。

　　从被调算法返回调用算法之前，系统也要完成三项工作： 

　　(1)保存被调算法的计算结果。 

　　(2)释放被调算法的数据区。 

　　(3)依照被调算法保存的返回地址将控制转移到调用算法。

　　分治法：将规模为n的问题分成k个规模为n/m的子问题去解 

　　分析如下图：

   

 

　　代码如下 

　　package com.wjl;

　　public class ChessBoard

　　{ 

　　int tile=1;//表示L型骨牌的编号 

　　int[][] board = new int[4][4];//表示棋盘 

　　//处理带有特殊棋子的棋盘.tr、tc表示棋盘的入口即左上角的行列号，dr、dc表示特殊棋子的行列位置，size表示棋盘的行数或者列数 

　　public void chessBoard(int tr, int tc, int dr, int dc, int size) 

　　{ 

　　if(size == 1) return; 

　　int t = tile++; 

　　System.out.println(t); 

　　int s = size/2;//每一次化大棋盘为一半的子棋盘 

　　//要处理带有特殊棋子的棋盘，第一步先处理左上棋盘 

　　if(dr < tr + s && dc< tc + s)//左上角子棋盘有特殊棋子 

　　chessBoard(tr,tc,dr,dc,s);//处理有特殊棋子的左上角子棋盘 

　　else//处理无特殊棋子的左上角子棋盘 

　　{ 

　　board[tr+s-1][tc+s-1] = t;//设左上角子棋盘的右下角为特殊棋子，用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 

　　{

 　　board[tr+s-1][tc+s] =t;//设右上角子棋盘的左下角为特殊棋子，用t型的骨牌覆盖。由于骨牌有三种，当处理过程中同一级设置的特殊棋子用相同的骨牌覆盖

　　chessBoard(tr,tc+s,tr+s-1,tc+s,s);//处理有用骨牌覆盖的格子作为特殊棋子的右上角子棋盘

　　}

　　//第三步处理左下角子棋盘 

　　if(dr >=tr+s && dc<tc+s) 左下角子棋盘有特殊棋子<="" p="">

 　　{

 　　chessBoard(tr+s,tc,dr,dc,s);//处理有特殊棋子的左下角子棋盘

 　　}

 　　else

 　　{

 　　board[tr+s][tc+s-1] = t;//设左下角子棋盘的右上角为特殊棋子，用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

　　{

　　board[tr+s][tc+s] = t;//设子棋盘右下角的左上角为特殊棋子，用t型的骨牌覆盖。由于骨牌有三种，当处理过程中同一级设置的特殊棋子用相同的骨牌覆盖

　　chessBoard(tr+s,tc+s,tr+s,tc+s,s);//处理有用 骨牌覆盖的格子作为特殊棋子的右下角子棋盘

　　}

　　}

　　public static void main(String[] args)

　　{ 

　　ChessBoard c = new ChessBoard();

　　c.chessBoard(0,0,1,1,4);

　　for(int i = 0; i <4; i++)

　　{ for(int j = 0; j <4; j++) 

　　System.out.print(c.board[i][j]+" ");

　　System.out.println(); 

　　} 

　　}

　　}

怎么样，通过课课家的讲解，是不是对Java懂的更多了呢？