利用分治思想实现一个棋牌覆盖的简单程序, 以复习分治法的内容.
- #include<iostream>
- #include<cmath>
- using namespace std;
- #define n 4
- int tile = 0;
- int board[n][n];
- void ChessBoardCover(int tr, int tc, int dr, int dc, int size);
- int main()
- {
- int a, b;
- cout <<"Input the position of the special check:" << endl;
- cin>> a>> b;
- ChessBoardCover(0,0,a,b,n);
- cout <<"Output the chessboard(0 represents the special one):" << endl;
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j < n; j++)
- cout << board[i][j] << " ";
- cout << endl;
- }
- getchar();
- getchar();
- }
- /*
- tile 是一个全局整形变量, 用来表示 L 形骨牌的编号, 初始值为 0.
- tr: 棋盘左上角方格的行号;
- tc: 棋盘左上角方格的列号;
- dr: 特殊方格所在的行号;
- dc: 特殊方格所在的列号;
- size:size = 2^k, 棋盘规格为 2^k*2^k
- */
- void ChessBoardCover(int tr, int tc, int dr, int dc, int size)
- {
- if (size == 1)
- return;
- int t = ++tile; // L 型骨牌号
- int s = size / 2; // 分割棋盘
- // 覆盖左上角子棋盘
- if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中
- ChessBoardCover(tr, tc, dr, dc, s);
- else
- {// 此棋盘中无特殊方格
- board[tr + s - 1][tc + s - 1] = t; // 用 t 号 L 型骨牌覆盖右下角
- ChessBoardCover(tr, tc, tr + s - 1, tc + s - 1, s); // 覆盖其余方格
- }
- // 覆盖右上角子棋盘
- if (dr < tr + s && dc>= tc + s) // 特殊方格在此棋盘中
- ChessBoardCover(tr, tc + s, dr, dc, s);
- else {// 此棋盘中无特殊方格
- board[tr + s - 1][tc + s] = t; // 用 t 号 L 型骨牌覆盖左下角
- // 覆盖其余方格
- ChessBoardCover(tr, tc + s, tr + s - 1, tc + s, s);
- }
- // 覆盖左下角子棋盘
- if (dr>= tr + s && dc <tc + s) // 特殊方格在此棋盘中
- ChessBoardCover(tr + s, tc, dr, dc, s);
- else
- {
- // 用 t 号 L 型骨牌覆盖右上角
- board[tr + s][tc + s - 1] = t;
- // 覆盖其余方格
- ChessBoardCover(tr + s, tc, tr + s, tc + s - 1, s);
- }
- // 覆盖右下角子棋盘
- if (dr>= tr + s && dc>= tc + s) // 特殊方格在此棋盘中
- ChessBoardCover(tr + s, tc + s, dr, dc, s);
- else
- {
- board[tr + s][tc + s] = t; // 用 t 号 L 型骨牌覆盖左上角
- ChessBoardCover(tr + s, tc + s, tr + s, tc + s, s); // 覆盖其余方格
- }
- }
作者: 耑新新, 发布于 博客园 https://home.cnblogs.com/u/Arthurian/
来源: http://www.bubuko.com/infodetail-3303004.html