分治求棋盘覆盖问题
骨牌每使用三次骨牌号应该加一,可是这样不能保证相同号的骨牌聚集在小棋盘的汇合处啊。这要怎么处理呢?
原题:http://
程序代码:
#include<stdio.h> int count ;//计数,骨牌号每用三次加一 int t=1 ; //L型骨牌的编号(递增) int board[100][100]; //棋盘 /***************************************************** * 递归方式实现棋盘覆盖算法 * 输入参数: * tr--当前棋盘左上角的行号 * tc--当前棋盘左上角的列号 * dr--当前特殊方格所在的行号 * dc--当前特殊方格所在的列号 * size:当前棋盘的:2^k *****************************************************/ void chessBoard ( int tr, int tc, int dr, int dc, int size ) { //每次递增1 int s=size/2; //棋盘中间的行、列号(相等的) if ( size==1 ) //棋盘方格大小为1,说明递归到最里层 return; if(count%3==0) t++; //检查特殊方块是否在左上角子棋盘中 if ( dr<tr+s && dc<tc+s ) //在 chessBoard ( tr, tc, dr, dc, s ); else //不在,将该子棋盘右下角的方块视为特殊方块 { board[tr+s-1][tc+s-1]=t; count++; 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; count++; 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 //不在,将该子棋盘右上角的方块视为特殊方块 { board[tr+s][tc+s-1]=t; count++; 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; count++; chessBoard ( tr+s, tc+s, tr+s, tc+s, s ); } } void main() { int size; int index_x,index_y; int i; int j; scanf("%d",&size); count=0; scanf("%d%d",&index_x,&index_y); chessBoard ( 0,0,index_x,index_y,size ,1); for ( i=0; i<size; i++ ) { for ( j=0; j<size; j++ ) printf("%d\t",board[i][j]); printf("\n"); } }