Number of Valid Move Combinations On Chessboard LeetCode solution in C++

1
class Solution {
2
 public:
3
  int bfs(vector<vector<int>> &positions, int move) {
4
    /*
5
        Position vector will contain 5 elements
6
        1. Inital x
7
        2. Inital y
8
        3. Direction of x
9
        4. Direction y
10
        5. steps to be moved (0 to 7)
11
    */
12
    int chessBoard[8][8]; // To maintain the state of board which cell is occupied
13
    memset(chessBoard, 0, sizeof(chessBoard));
14
    bool isVal = false; // To track if any element can be moved
15
    for (vector<int> &pos : positions) {
16
      int x = pos[0] + pos[4] * pos[2], y = pos[1] + pos[4] * pos[3];
17
      if (pos[4] > move) {
18
        isVal = true;
19
        x = pos[0] + move * pos[2], y = pos[1] + move * pos[3];
20
      }
21
      if (x < 0 || x > 7 || y < 0 || y > 7) return 0;
22
      chessBoard[x][y]++;
23
    }
24
    for (int i = 0; i < 8; i++)
25
      for (int j = 0; j < 8; j++)
26
        if (chessBoard[i][j] > 1) return 0; // More than one element
27
    int ret = 0;
28
    if (!isVal)
29
      ret = 1;
30
    else
31
      ret = bfs(positions, move + 1);
32
    return ret;
33
  }
34
  int dfs(int idx, vector<string> &pieces, vector<vector<int>> &positions) {
35
    if (idx >= pieces.size()) return bfs(positions, 0);
36
    int ret = 0;
37
    positions[idx].push_back(0);
38
    positions[idx].push_back(0);
39
    positions[idx].push_back(0);
40
    ret += dfs(idx + 1, pieces, positions); // When we decide piece will not move
41
    positions[idx].pop_back();
42
    positions[idx].pop_back();
43
    positions[idx].pop_back();
44
    // When piece will move in choosen direction.
45
    if (pieces[idx] == "rook" || pieces[idx] == "queen") {
46
      for (int x = -1; x <= 1; x++)
47
        if (x != 0) {
48
          for (int moves = 1; moves < 8; moves++) {
49
            int dx = positions[idx][0] + moves * x;
50
            if (dx >= 0 && dx < 8) {
51
              positions[idx].push_back(x);
52
              positions[idx].push_back(0);
53
              positions[idx].push_back(moves);
54
              ret += dfs(idx + 1, pieces, positions);
55
              positions[idx].pop_back();
56
              positions[idx].pop_back();
57
              positions[idx].pop_back();
58
            }
59
          }
60
        }
61
      for (int y = -1; y <= 1; y++)
62
        if (y != 0) {
63
          for (int moves = 1; moves < 8; moves++) {
64
            int dx = positions[idx][1] + moves * y;
65
            if (dx >= 0 && dx < 8) {
66
              positions[idx].push_back(0);
67
              positions[idx].push_back(y);
68
              positions[idx].push_back(moves);
69
              ret += dfs(idx + 1, pieces, positions);
70
              positions[idx].pop_back();
71
              positions[idx].pop_back();
72
              positions[idx].pop_back();
73
            }
74
          }
75
        }
76
    }
77
    if (pieces[idx] == "bishop" || pieces[idx] == "queen") {
78
      for (int x = -1; x <= 1; x++)
79
        if (x != 0)
80
          for (int y = -1; y <= 1; y++)
81
            if (y != 0) {
82
              for (int moves = 1; moves < 8; moves++) {
83
                int dx = positions[idx][0] + moves * x;
84
                int dy = positions[idx][1] + moves * y;
85
                if (dx >= 0 && dx < 8 && dy >= 0 && dy < 8) {
86
                  positions[idx].push_back(x);
87
                  positions[idx].push_back(y);
88
                  positions[idx].push_back(moves);
89
                  ret += dfs(idx + 1, pieces, positions);
90
                  positions[idx].pop_back();
91
                  positions[idx].pop_back();
92
                  positions[idx].pop_back();
93
                }
94
              }
95
            }
96
    }
97
    return ret;
98
  }
99
  int countCombinations(vector<string> &pieces, vector<vector<int>> &positions) {
100
    for (vector<int> &pos : positions) pos[0]--, pos[1]--;
101
    return dfs(0, pieces, positions);
102
  }
103
};