棋盤覆蓋，棋盤覆蓋問題

棋盤覆蓋，棋盤覆蓋問題

 1 /**
 2 *棋盤覆蓋  分治策略
 3 *Author: ChengSong
 4 *Time:2015/12/8 18:55
 5 */
 6 
 7 #include <iostream>
 8 #include <cstdio>
 9 using namespace std;
10 int tag = 1;
11 void chessboard(int board[][20],int tr,int tc,int dr,int dc,int size){
12     if(size==1)
13         return;
14     int s = size/2;
15     int t = tag++;
16     if(dr<tr+s&&dc<tc+s){
17         chessboard(board,tr,tc,dr,dc,s);
18     }else{
19         board[tr+s-1][tc+s-1] = t;
20         chessboard(board,tr,tc,tr+s-1,tc+s-1,s);
21     }
22     if(dr>=tr+s&&dc<tc+s){
23         chessboard(board,tr+s,tc,dr,dc,s);
24     }
25     else{
26         board[tr+s][tc+s-1] = t;
27         chessboard(board,tr+s,tc,tr+s,tc+s-1,s);
28     }
29     if(dr>=tr+s&&dc>=tc+s){
30         chessboard(board,tr+s,tc+s,dr,dc,s);
31     }
32     else{
33         board[tr+s][tc+s] = t;
34         chessboard(board,tr+s,tc+s,tr+s,tc+s,s);
35     }
36     if(dr<tr+s&&dc>=tc+s){
37         chessboard(board,tr,tc+s,dr,dc,s);
38     }
39     else{
40         board[tr+s-1][tc+s] = t;
41         chessboard(board,tr,tc+s,tr+s-1,tc+s,s);
42     }
43 }
44 int main(){
45     int size;
46     int board[20][20];
47     cin>>size;
48     int row,col;
49     cin>>row>>col;
50     board[row-1][col-1] = 0;
51     chessboard(board,0,0,row-1,col-1,size);
52     for(int i=0;i<size;++i){
53         for(int j=0;j<size;++j){
54             printf("%d ",board[i][j]);
55         }
56         printf("\n");
57     }
58     return 0;
59 }