Cerinta completa

You are given a grid having N rows and M columns. A grid square can either be blocked or empty. Blocked squares are represented by a ‘#’ and empty squares are represented by ‘.’. Find the number of ways to tile the grid using L shaped bricks. A L brick has one side of length three units while other of length 2 units. All empty squares in the grid should be covered by exactly one of the L shaped tiles, and blocked squares should not be covered by any tile. The bricks can be used in any orientation (they can be rotated or flipped).

Input Format

The first line contains the number of test cases T. T test cases follow. Each test case contains N and M on the first line, followed by N lines describing each row of the grid.

Constraints

1 <= T <= 50
1 <= N <= 20
1 <= M <= 8
Each grid square will be either ‘.’ or ‘#’.

Output Format

Output the number of ways to tile the grid. Output each answer modulo 1000000007.

Sample Input

3  
2 4  
....  
....  
3 3  
...  
.#.  
...  
2 2  
##  
##

Sample Output

2  
4  
1

Explanation

NOTE:
If all points in the grid are blocked the number of ways is 1, as in the last sample testcase.

Limbajul de programare folosit: cpp14

Cod:

// https://www.hackerrank.com/challenges/brick-tiling

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;
const int MOD = 1000000007, inf = 0x3f3f3f3f, maxn = 25, maxs = 1 << 8;
LL dp[maxn][maxs][maxs];
int state[maxn], cur, nxt, n, m, initJ, initK;

bool is_valid(int mask, int pos) {
    return (mask & (1 << pos)) == 0;
}

void dfs(int dep, int s1, int s2, int s3, int current) {
    if (current >= (1 << m)) return;

    if (current == (1 << m) - 1) {
        dp[nxt][s2][s3] = (dp[nxt][s2][s3] + dp[cur][initJ][initK]) % MOD;
        return;
    }

    if (s1 & (1 << dep))
        dfs(dep + 1, s1, s2, s3, current);
    else {
        if (dep + 1 < m && is_valid(s2, dep) && is_valid(s3, dep) && is_valid(s3, dep + 1))
            dfs(dep + 1, s1, s2 | (1 << dep), s3 | (1 << dep) | (1 << (dep + 1)), current | (1 << dep));

        if (dep >= 1 && is_valid(s2, dep) && is_valid(s3, dep) && is_valid(s3, dep - 1))
            dfs(dep + 1, s1, s2 | (1 << dep), s3 | (1 << dep) | (1 << (dep - 1)), current | (1 << dep));

        if (dep + 1 < m && is_valid(s1, dep + 1) && is_valid(s2, dep + 1) && is_valid(s3, dep + 1))
            dfs(dep + 2, s1, s2 | (1 << (dep + 1)), s3 | (1 << (dep + 1)), current | (1 << dep) | (1 << (dep + 1)));

        if (dep + 1 < m && is_valid(s1, dep + 1) && is_valid(s2, dep) && is_valid(s3, dep))
            dfs(dep + 2, s1, s2 | (1 << dep), s3 | (1 << dep), current | (1 << dep) | (1 << (dep + 1)));

        if (dep + 2 < m && is_valid(s2, dep) && is_valid(s2, dep + 1) && is_valid(s2, dep + 2))
            dfs(dep + 1, s1, s2 | (1 << dep) | (1 << (dep + 1)) | (1 << (dep + 2)), s3, current | (1 << dep));

        if (dep >= 2 && is_valid(s2, dep) && is_valid(s2, dep - 1) && is_valid(s2, dep - 2))
            dfs(dep + 1, s1, s2 | (1 << (dep - 2)) | (1 << (dep - 1)) | (1 << dep), s3, current | (1 << dep));

        if (dep + 2 < m && is_valid(s2, dep) && is_valid(s1, dep + 1) && is_valid(s1, dep + 2))
            dfs(dep + 3, s1, s2 | (1 << dep), s3, current | (1 << dep) | (1 << (dep + 1)) | (1 << (dep + 2)));

        if (dep + 2 < m && is_valid(s1, dep + 1) && is_valid(s1, dep + 2) && is_valid(s2, dep + 2))
            dfs(dep + 3, s1, s2 | (1 << (dep + 2)), s3, current | (1 << dep) | (1 << (dep + 1)) | (1 << (dep + 2)));
    }
}

char str[10];

int main() {
    int ts;

    cin >> ts;

    while (ts--) {
        memset(state, 0, sizeof(state));
        cin >> n >> m;

        for (int i = 1; i <= n; i++) {
            cin >> str;

            for (int j = 0; j < m; j++)
                if (str[j] == '#')
                    state[i] |= (1 << j);
        }

        if (n == 1) {
            if (state[1] == (1 << m) - 1) puts("1");
            else puts("0");
            continue;
        }

        memset(dp, 0, sizeof(dp));
        dp[2][state[1]][state[2]] = 1;

        for (int i = 2; i <= n; i++) {
            cur = i, nxt = i + 1;

            for (int j = 0; j < (1 << m); j++) {
                for (int k = 0; k < (1 << m); k++) {
                    if (dp[cur][j][k] == 0) continue;
                    initJ = j; initK = k;
                    dfs(0, j, k, state[i + 1], j);
                }
            }
        }

        cout << dp[n + 1][(1 << m) - 1][0] << endl;
    }

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464612692

Link challenge: https://www.hackerrank.com/challenges/brick-tiling/problem

Brick Tiling