盖游戏板问题

题目：
有一个H*W大小的游戏板，由黑白两种格子组成。现要用3个单位格子的L状板块把白色格子全部覆盖掉。板块可以自由旋转，但不能重叠覆盖黑色格子，或超出游戏版。
计算对给定游戏板有几种覆盖方法。

解决思路：
此题也属于计算组合个数的问题。因此，通过穷举搜索法计算出能够覆盖游戏板的所有可能的组合来解决此问题。首先要处理给定游戏板的白色格子不是3的倍数的情况，此时不可能存在答案，所以要单独处理。之后把白色格子除以3，得到盖上白色格子所需的L型板块数量M。现在可以把整个求解个过程分解为N个小的操作，每个操作视为是放置1个板块。利用递归函数，首先在给定的游戏板中放置1块板块，剩余的将使用递归调用的方式覆盖。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define ul unsigned long long
#define ll long long
#define For(i,a,b) for(int i=a;i>&board,int y ,int x,int type,int delta){
    bool ok = true;
    for(int i=0;i<3;++i){
        const int ny = y+coverType[type][i][10];
        const int nx = x+coverType[type][i][1];
        if(ny<0||ny>=board.size()||nx<0||nx>=board[0].size())
            ok = false;
        else if((board[ny][nx]+=delta)>1)
            ok = false;
    }
    return ok;
}

//返回覆盖borad 种保存着的所有空格的方法总数。
//board[i][j] = 1 表示已经覆盖的格子或者黑色格子
//board[i][j] = 0 表示未被覆盖的白色格子
int cover(vector>&board){
    int y = -1,x = -1;
    // 在剩余没有被覆盖的白色格子中，寻找最左上角的格子
    for(int i=0;i>c;
    int H,W;
    vector> board;
    vector v;
    while (c--) {
        scanf("%d %d",&H,&W);
        board.clear();
        for(int i=0;i>temp;
                if(temp=='#')v.push_back(1);
                else if(temp=='.')v.push_back(0);
            }
            
            board.push_back(v);
        }
        int ret=0;
        ret=cover(board);
        cout<

盖游戏板问题

C/C++/C#相关栏目本月热门文章