棋盘分治

本文主要是介绍棋盘分治，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>  /*
(tr, tc): 棋盘左上角的行号，列号
(dr, dc): 棋盘右上角的行号，列号
size：当前棋盘的大小 = 2 ^k
*/#define EDGE_LEN 8
int board[EDGE_LEN][EDGE_LEN];
int title = 0;void putArray()
{for(int i = 0; i < EDGE_LEN; i++){for(int j = 0; j < EDGE_LEN; j++){printf("%4d", board[i][j]);}printf("\n");}
}void chessBoard(int tr, int tc, int dr, int dc, int size)
{if(size == 1)return;int s = size / 2; //分割棋盘，长宽都变为一半int t =  ++title; //L型骨牌的编号//如果L型骨牌在左上角if(dr < tr + s && dc < tc + s)chessBoard(tr, tc, dr, dc, s);else//否则将其右下角填充(是Ｌ型骨牌的一部分，与另外三个不存在特殊方格的形成Ｌ型骨牌)，构造一个特殊方格{board[tr + s - 1][tc + s - 1] = 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;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;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;chessBoard(tr + s, tc + s, tr + s, tc + s, s);}
}int main()
{for(int i = 0; i < EDGE_LEN; i++){for(int j = 0; j < EDGE_LEN; j++){board[i][j] = -1;}}board[0][0] = 0;chessBoard(0, 0, 0, 0, EDGE_LEN );putArray();system("pause");return 0;
}

详情，请参考《苏犯法设计与分析》

这篇关于棋盘分治的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---