LITS 游戏 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 100 + 100;
vector<vector<string>> G = {
    // L
    {
        "10",
        "10",
        "11"
    },
    {
        "111",
        "100"
    },
    {
        "11",
        "01",
        "01"
    },
    {
        "001",
        "111"
    },
    // I
    {
        "1111"
    },
    {
        "1",
        "1",
        "1",
        "1"
    },
    // T
    {
        "111",
        "010"
    },
    {
        "01",
        "11",
        "01"
    },
    {
        "010",
        "111"
    },
    {
        "10",
        "11",
        "10"
    },
    // S
    {
        "011",
        "110"
    },
    {
        "10",
        "11",
        "01"
    }
};

int T, n, nn, x;
bool flag;
int status[12] = {0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 3, 3};
char ch[13] = "LLLLIITTTTSS";
char str[maxn][maxn];
int pos[12][4][2];

void init() {
    for (int i = 0; i < 12; ++i) {
        int idx = 0;
        for (int j = 0; j < G[i].size(); ++j) {
            for (int k = 0; k < G[i][j].length(); ++k) {
                if (G[i][j][k] == '1') {
                    pos[i][idx][0] = j;
                    pos[i][idx][1] = k;
                    ++idx;
                }
            }
        }
    }
}

bool in(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n;
}

bool canPut(int x, int y, int idx) {
    for (int i = 0; i < 4; ++i) {
        int xx = x + pos[idx][i][0];
        int yy = y + pos[idx][i][1];
        if (!in(xx, yy) || str[xx][yy] != '*') {
            return false;
        }
    }
    return true;
}

void put(int x, int y, int idx, char ch) {
    for (int i = 0; i < 4; ++i) {
        int xx = x + pos[idx][i][0];
        int yy = y + pos[idx][i][1];
        str[xx][yy] = ch;
    }
}

void dfs(int depth, int s) {
    if (depth == nn) {
        if (s == 15) {
            flag = true;
        }
        return ;
    }
    int x = depth / n;
    int y = depth % n;
    for (int i = 0; i < 12; ++i) {
        if ((s & (1 << status[i])) == 0 && canPut(x, y, i)) {
            put(x, y, i, ch[i]);
            dfs(depth + 1, s | (1 << status[i]));
            if (flag) {
                return ;
            }
            put(x, y, i, '*');
        }
    }
    dfs(depth + 1, s);
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    init();
    cin >> T;
    while (T--) {
        cin >> n;
        nn = n * n;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> x;
                str[i][j] = (x == 1 ? '*' : '.');
            }
        }
        flag = false;
        dfs(0, 0);
        cout << (flag ? "Yes" : "No") << endl;
    }

    return 0;
}