algorithm/Algorithm/cpp/2056.NumberofValidMoveCombinationsOnChessboard/countCombinations.cpp at master · wuvei/algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
public:
    void dfs(int cur, bool vis[8][8][8]) {
        if (cur == n) {
            ++res;
            return;
        }
        int x = poss[cur][0] - 1, y = poss[cur][1] - 1;

        // move.
        vector<pair<int, int>> dirs;
        if (ps[cur] == "rook") {
            dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        } else if (ps[cur] == "queen") {
            dirs = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        } else {
            dirs = {{-1, -1}, {1, 1}, {-1, 1}, {1, -1}};
        }
        for (int i = 0; i < dirs.size(); ++i) {
            int dx = dirs[i].first, dy = dirs[i].second;
            for (int j = 1; ; ++j) {
                int xx = x + dx * j;
                int yy = y + dy * j;
                if (xx < 0 || xx >= 8 || yy < 0 || yy >= 8 || vis[j][xx][yy]) {
                    while (--j >= 1) {
                        int xx = x + dx * j;
                        int yy = y + dy * j;
                        vis[j][xx][yy] = false;
                    }
                    break;
                }
                vis[j][xx][yy] = true;
                bool ok = true;
                for (int k = j + 1; k < 8; ++k) {
                    if (vis[k][xx][yy]) {
                        ok = false;
                        break;
                    }
                }
                if (!ok)
                    continue;
                for (int k = j; k < 8; ++k) {
                    vis[k][xx][yy] = true;
                }
                dfs(cur + 1, vis);
                for (int k = j + 1; k < 8; ++k) {
                    vis[k][xx][yy] = false;
                }
            }
        }

        // stay.
        bool ok = true;
        for (int i = 1; i < 8; ++i)
            if (vis[i][x][y]) {
                ok = false;
                break;
            }
        if (!ok)
            return;
        for (int i = 1; i < 8; ++i)
            vis[i][x][y] = true;
        dfs(cur + 1, vis);
        for (int i = 1; i < 8; ++i)
            vis[i][x][y] = false;
    }

    int countCombinations(vector<string>& pieces, vector<vector<int>>& positions) {
        res = 0;
        ps = pieces;
        poss = positions;
        n = ps.size();
        bool vis[8][8][8] = {0};
        dfs(0, vis);
        return res;
    }

    int n;
    int res;
    vector<string> ps;
    vector<vector<int>> poss;
};