1

我正在尝试解决这个问题，但我找不到解决方案：

给出一个由排列成 N 行 M 列的正方形组成的棋盘。这块板的平铺是覆盖它的瓷砖图案。如果满足以下条件，则平铺很有趣：

    only tiles of size 1x1 and/or 2x2 are used;
    each tile of size 1x1 covers exactly one whole square;
    each tile of size 2x2 covers exactly four whole squares;
    each square of the board is covered by exactly one tile.

例如，以下图像显示了一块 4 行 3 列的板的一些有趣的平铺：http: //dabi.altervista.org/images/task.img.4x3_tilings_example.gif

如果棋盘上至少存在一个正方形，其中一个棋盘上覆盖有大小为 1x1 的棋子，而另一个棋盘上覆盖着大小为 2x2 的棋子，则棋盘的两个有趣的棋子是不同的。例如，上图中显示的所有平铺都是不同的。

写一个函数

int count_tilings(int N, int M);

即，给定两个整数 N 和 M，返回大小为 N 行和 M 列的板的不同有趣平铺数量的余数模 10,000,007。

假使，假设：

    N is an integer within the range [1..1,000,000];
    M is an integer within the range [1..7].

例如，给定 N = 4 和 M = 3，函数应该返回 11，因为大小为 4 行和 3 列的板有 11 个不同的有趣平铺：

http://dabi.altervista.org/images/task.img.4x3_tilings_all.gif

对于（4,3），结果是 11，对于（6,5），结果是 1213。我尝试了以下方法，但它不起作用：

static public int count_tilings ( int N,int M ) {

    int result=1;
    if ((N==1)||(M==1)) return 1;

    result=result+(N-1)*(M-1);

    int max_tiling=  (int) ((int)(Math.ceil(N/2))*(Math.ceil(M/2)));
    System.out.println(max_tiling);
    for (int i=2; i<=(max_tiling);i++){
        if (N>=2*i){
            int n=i+(N-i);
            int k=i;
            //System.out.println("M-1->"+(M-1) +"i->"+i);
            System.out.println("(M-1)^i)->"+(Math.pow((M-1),i)));
            System.out.println( "n="+n+ " k="+k);
            System.out.println(combinations(n, k));
            if (N-i*2>0){
                result+= Math.pow((M-1),i)*combinations(n, k);
            }else{
                result+= Math.pow((M-1),i);
            }
        }
        if (M>=2*i){
            int n=i+(M-i);
            int k=i;
            System.out.println("(N-1)^i)->"+(Math.pow((N-1),i)));
            System.out.println( "n="+n+ " k="+k);
            System.out.println(combinations(n, k));
            if (M-i*2>0){
                result+= Math.pow((N-1),i)*combinations(n, k);
            }else{
                result+= Math.pow((N-1),i);
            }
        }

    }
    return result;
}
static long combinations(int n, int k) {
    /*binomial coefficient*/
    long coeff = 1;
    for (int i = n - k + 1; i <= n; i++) {
        coeff *= i;
    }
    for (int i = 1; i <= k; i++) {
        coeff /= i;
    }
    return coeff;
}
4

2 回答 2

2

由于这是家庭作业，我不会给出完整的解决方案，但我会给你一些提示。

首先这是一个递归解决方案：

class Program
{
    // Important note:
    // The value of masks given here is hard-coded for m == 5.
    // In a complete solution, you need to calculate the masks for the
    // actual value of m given. See explanation in answer for more details.

    int[] masks = { 0, 3, 6, 12, 15, 24, 27, 30 };

    int CountTilings(int n, int m, int s = 0)
    {
        if (n == 1) { return 1; }

        int result = 0;
        foreach (int mask in masks)
        {
            if ((mask & s) == 0)
            {
                result += CountTilings(n - 1, m, mask);
            }
        }
        return result;
    }

    public static void Main()
    {
        Program p = new Program();
        int result = p.CountTilings(6, 5);
        Console.WriteLine(result);
    }
}

在线查看它：ideone

请注意，我添加了一个额外的参数s。这存储了第一列的内容。如果第一列为空，则 s = 0。如果第一列包含一些实心方块，则设置 s 中的相应位。最初 s = 0，但是当放置一个 2 x 2 的瓷砖时，这会填充下一列中的一些方块，这意味着 s 在递归调用中将是非零的。

该masks变量是硬编码的，但在完整的解决方案中，它需要根据 的实际值来计算m。如果您查看它们的二进制表示，则存储的值masks更有意义：

00000
00011
00110
01100
01111
11000
11011
11110

换句话说，它是在具有 m 位的二进制数中设置位对的所有方法。您可以编写一些代码来生成所有这些可能性。或者由于 m 只有 7 种可能的值，您也可以将所有 7 种可能性硬编码为masks.

然而，递归解决方案存在两个严重问题。

  1. 对于较大的值，它将溢出堆栈N。
  2. 它需要指数时间来计算。即使对于较小的值，它也非常慢N

这两个问题都可以通过将算法重写为迭代来解决。保持m不变并初始化ton = 1的所有可能值的结果。这是因为如果您只有一列，则只能使用 1x1 的图块，并且只有一种方法可以做到这一点。s1

现在，您可以使用 的结果来计算n = 2的所有可能值。可以重复此操作，直到达到. 该算法在关于 的线性时间内完成，并且需要恒定的空间。sn = 1n = NN

于 2012-08-25T17:40:48.413 回答
0

这是一个递归解决方案：

// time used : 27 min
#include <set>
#include <vector>
#include <iostream>
using namespace std;
void placement(int n, set< vector <int> > & p){
    for (int i = 0; i < n -1 ; i ++){
        for (set<vector<int> > :: iterator j  = p.begin(); j != p.end(); j ++){
            vector <int> temp = *j;
            if (temp[i] == 1 || temp[i+1] == 1) continue;
            temp[i] = 1; temp[i+1] = 1;
            p.insert(temp);
        }
    }
}

vector<vector<int> > placement( int n){
    if (n > 7) throw "error";
    set <vector <int> > p;
    vector <int> temp (n,0);
    p.insert (temp);
    for (int i = 0; i < 3; i ++) placement(n, p);
    vector <vector <int> > s;
    s.assign (p.begin(), p.end());
    return s;
}


bool tryput(vector <vector <int> > &board, int current, vector<int> & comb){
    for (int i = 0; i < comb.size(); i ++){
        if ((board[current][i] == 1 || board[current+1][i]) && comb[i] == 1) return false;
    }
    return true;
}
void  put(vector <vector <int> > &board, int current, vector<int> & comb){
    for (int i = 0; i < comb.size(); i ++){
        if (comb[i] == 1){
            board[current][i] = 1;
            board[current+1][i] = 1;
        }
    }
    return;
}

void  undo(vector <vector <int> > &board, int current, vector<int> & comb){
    for (int i = 0; i < comb.size(); i ++){
        if (comb[i] == 1){
            board[current][i] = 0;
            board[current+1][i] = 0;
        }
    }
    return;
}



int place (vector <vector <int> > &board, int current,  vector < vector <int> >  & all_comb){
    int m = board.size();
    if (current >= m) throw "error";
    if (current == m - 1) return 1;
    int count = 0;
    for (int i = 0; i < all_comb.size(); i ++){
        if (tryput(board, current, all_comb[i])){
            put(board, current, all_comb[i]);
            count += place(board, current+1, all_comb) % 10000007;
            undo(board, current, all_comb[i]);
        }
    }
    return count;
}
int place (int m, int n){
    if (m == 0) return 0;
    if (m == 1) return 1;
    vector < vector <int> > all_comb = placement(n);
    vector <vector <int> > board(m, vector<int>(n, 0));
    return place (board, 0, all_comb);

}
int main(){
    cout << place(3, 4) << endl;
    return 0;
}

时间复杂度O(n^3 * exp(m))

减少空间使用尝试位向量。

为了降低时间复杂度O(m*(n^3))，尝试动态规划。

为了降低时间复杂度，O(log(m) * n^3)尝试分治+动态规划。

祝你好运

于 2012-08-30T07:36:41.877 回答