shengqiang's blog

棋盘覆盖问题

 
  • 2017年 07月08日

##大致思路：

  1. 运用分治法思想，每次将棋盘分成4个边长为2^k-1的小棋盘 依次判断在每个小棋盘中，特殊方块是否在其中，若在，则继续递归，直到边长为1
  2. 若不再，则根据小棋盘的位置，将某个小棋盘内的对应的方块设置为特殊方块（若小棋盘在左上角，则设置右下角为特殊方块；若小棋盘在左下角，则设置右上角为特殊方块；若小棋盘在右边上角，则设置左下角为特殊方块；若小棋盘在右下角，则设置左上角为特殊方块；），然后继续递归，直到边长为1。
  3. 当递归层层退出到第一层时，棋盘覆盖完毕。

##主函数:

  1. 定义变量size,row,column
  2. 使用户输入矩阵大小size，特殊方块的行号、列号
  3. 判断输入的数据的合法性，若合法，调用Chess(0, 0, row, column, size);函数，并依次循环，显示覆盖情况；若不合法，则要求用户重新输入，直到合法为止。

##Chess(…)函数:

  1. 首先，判断size是否等于1，若是则结束，否则另s等于size/2，代表中间长度。同时，用t记录L型骨牌的编号。
  2. 依次检查每个小棋盘中是否存在特殊方块，检查方法如下：
  3. 通过判断特殊方块与小棋盘的坐标大小，判定是否存在该小棋盘中
  4. 若是，则继续递归，直到size等于1；
  5. 否则，则根据相应情况，设置相应位置的方块为特殊方块（具体方法，上面的思路已经说了），并继续递归，直到size等于1

##代码部分：

// Chess.cpp : 定义控制台应用程序的入口点。
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

int nCount = 0;//L型骨牌编号
int Array[100][100] = {0};

void Chess(int tr, int tc, int dr, int dc, int size)
{
    //tr和tc代表矩阵左上角的坐标
    int s, t;
    if (1 == size) return;//直到棋盘的方格为1，分治结束条件

    s = size / 2; //棋盘中间长度
    t = ++nCount;//L型骨牌编号

    //检查特殊方块是否在左上角
    if (dr < tr + s && dc < tc + s)
    {
        Chess(tr, tc, dr, dc, s);
    }
    else//将子棋盘右下角设置为特殊方块
    {
        Array[tr + s - 1][tc + s - 1] = t;
        Chess(tr, tc, tr + s - 1, tc + s - 1, s);
    }

    //检查特殊方块是否在右上角
    if (dr < tr + s && dc >= tc + s)
    {
        Chess(tr, tc + s, dr, dc, s);
    }
    else//将子棋盘左下角设置为特殊方块
    {
        Array[tr + s - 1][tc + s] = t;
        Chess(tr, tc + s, tr + s - 1, tc + s, s);
    }

    //检查特殊方块是否在左下角
    if (dr >= tr + s && dc < tc + s)
    {
        Chess(tr + s, tc, dr, dc, s);
    }
    else//将子棋盘右上角设置为特殊方块
    {
        Array[tr + s][tc + s - 1] = t;
        Chess(tr + s, tc, tr + s, tc + s - 1, s);
    }

    //检查特殊方块是否在右下角
    if (dr >= tr + s && dc >= tc + s)
    {
        Chess(tr + s, tc + s, dr, dc, s);
    }
    else//将子棋盘左上角设置为特殊方块
    {
        Array[tr + s][tc + s] = t;
        Chess(tr + s, tc + s, tr + s, tc + s, s);
    }

}

int main(void)
{
    int size, row, column;//矩阵大小,行号,列号
    int i, j;
    printf("请输入矩阵大小N\n");
    while (scanf("%d", &size) != 1)
    {
        printf("请输入一个整数矩阵大小N\n");
        while (getchar() != '\n'); //读取字符 到换行为止。		
    }
    printf("请输入行号row\n");
    while (scanf("%d", &row) != 1)
    {
        printf("请输入一个整数行号大小N\n");
        while (getchar() != '\n'); //读取字符 到换行为止。		
    }
    printf("请输入列号column\n");
    while (scanf("%d", &column) != 1)
    {
        printf("请输入一个整数列号大小N\n");
        while (getchar() != '\n'); //读取字符 到换行为止。		
    }

    Chess(0, 0, row, column, size);

    for (i = 0; i < size; i++)
    {
        for (j = 0; j < size; j++)
            printf("%2d ", Array[i][j]);
        printf("\n");
    }
    system("pause");
    return 0;

}
搜索