首页 > 代码库 > 递归分治解决棋盘覆盖问题
递归分治解决棋盘覆盖问题
package algorithm; //递归分治解决棋盘覆盖问题 public class ChessBoard { //tr棋盘左上角方格的行号 //tc棋盘左上角方格的列号 //size = 2^k棋盘规格为2^k *2^k //dr特殊方格所在的行号 //dc特殊方格所在的列号 private static int tile = 0;//L型骨牌号 public static int[][] Board = new int[100][100]; public static void chessBoard(int tr,int tc,int dr,int dc,int size){ if(size == 1) return; size/=2; int t = ++tile; //特殊方格在左上角 if(dr < tr + size&&dc < tc + size){ chessBoard(tr,tc,dr,dc,size); }else{ Board[tr + size - 1][tc + size -1] = t; chessBoard(tr,tc,tr + size -1,tc + size -1,size); } //特殊方格在右上角 if(dr < tr + size&&dc >= tc + size){ chessBoard(tr ,tc + size,dr,dc,size); }else{ Board[tr + size - 1][tc + size] = t; chessBoard(tr,tc + size,tr + size - 1,tc + size,size); } //特殊方格在左下角 if(dr >= tr + size&&dc < tc + size){ chessBoard(tr + size,tc,dr,dc,size); }else{ Board[tr + size][tc + size -1] = t; chessBoard(tr + size,tc,tr + size,tc + size -1,size); } //特殊方格在右下角 if(dr >= tr + size&&dc >= tc + size){ chessBoard(tr + size,tc + size,dr,dc,size); }else{ Board[tr + size][tc + size] = t; chessBoard(tr + size,tc + size,tr + size,tc + size,size); } } public static void main(String[] args) { // TODO Auto-generated method stub int size = 8; chessBoard(0,0,3,3,size); for(int i = 0;i < size;i++){ for(int j = 0;j < size;j++){ String s = String.format("%3d",Board[i][j]); System.out.print(s); } System.out.println(); } } }
递归分治解决棋盘覆盖问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。