[科技论文网] http://www.scipapers.com    2007-12-01  

分治法解决棋盘覆盖问题

作者：李锐

棋盘覆盖问题的解法，使用C语言写成，放在这里是为了以后忘记了可以拿过来看看。

/**//*
 * ============================================================================
 * 
 *        Filename:  chess_board.c
 * 
 *     Description:  the solution of chess board's coverage
 * 
 *         Version:  1.0
 *         Created:  09/16/06 22:37:43 CST
 *        Revision:  none
 *        Compiler:  gcc
 * 
 *          Author:  lirui (colin), lirui@ncic.ac.cn
 *         Company:  asl.ncic.ac.cn
 * 
 * ============================================================================
 */
 
#include <stdio.h>
 
#define MAXSIZE 1<<10
 
int chess[MAXSIZE][MAXSIZE];
void chess_board(int tr, int tc, int dr, int dc, int size)
...{
    static int tile = 1;
 
    if(1==size) return;
 
    int t = tile++;
    int s = (size>>1);
 
    /**//* ---- left-up corner ---- */
    if(dr<tr+s && dc<tc+s)...{
        chess_board(tr, tc, dr, dc, s);
    } else ...{
        chess[tr+s-1][tc+s-1] = t;
        chess_board(tr, tc, tr+s-1, tc+s-1, s);
    }
 
    /**//* ---- right-up corner --- */
    if(dr<tr+s && dc>=tc+s)...{
        chess_board(tr, tc+s, dr, dc, s);
    } else ...{
        chess[tr+s-1][tc+s] = t;
        chess_board(tr, tc+s, tr+s-1, tc+s, s);
    }
 
    /**//* ---- left-down corner--- */
    if(dr>=tr+s && dc<tc+s)...{
        chess_board(tr+s, tc, dr, dc, s);
    } else ...{
        chess[tr+s][tc+s-1] = t;
        chess_board(tr+s, tc, tr+s, tc+s-1, s);
    }
 
    /**//* ---- right-down corner-- */
    if(dr>=tr+s && dc>=tc+s)...{
        chess_board(tr+s, tc+s, dr, dc, s);
    } else ...{
        chess[tr+s][tc+s] = t;
        chess_board(tr+s, tc+s, tr+s, tc+s, s);
    }
}
 
void print_chess(int size)
...{
    int i, j;
    for(i = 0; i<size; i++)...{
        for(j=0; j<size; j++)
            printf("%4d", chess[i][j]);
        printf(" ");
    }
}
 
int main( int argc, char *argv[] )
...{
    chess_board(0, 0, 1, 2, 16);
    print_chess(16);
        return 0;
}   /**//* ----------  end of function main  ---------- */



    来源：

声明：本文由网友推荐或作者提交，版权归原作者所有，刊登此文仅为传播知识，展示研究成果，提高文章引用率。未经原作者授权，禁止用于任何形式的商业行为。科技论文网倡导尊重知识、尊重劳动、保护原创、知识共享。由于部分论文文章来于网络，文章作者不祥，请相关的原创作者与我们联系，以便加上您的署名。