Check if Word Can Be Placed In Crossword LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool placeWordInCrossword(vector<vector<char>> &board, string word) {
4
    int m = board.size();
5
    int n = board[0].size();
6
    for (int i = 0; i < m; i++) {
7
      for (int j = 0; j < n; j++) {
8
        if (board[i][j] != '#') {
9
          if (valid(board, i - 1, j) && check(board, word, i, j, 0, true, 1)) return true;
10
          if (valid(board, i + 1, j) && check(board, word, i, j, 0, true, -1)) return true;
11
          if (valid(board, i, j - 1) && check(board, word, i, j, 0, false, 1)) return true;
12
          if (valid(board, i, j + 1) && check(board, word, i, j, 0, false, -1)) return true;
13
        }
14
      }
15
    }
16
    return false;
17
  }
18

19
  bool check(vector<vector<char>> &board, string &word, int x, int y, int pos, bool vertical,
20
             int inc) {
21
    if (pos == word.size()) {
22
      if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return true;
23
      return board[x][y] == '#';
24
    }
25
    if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return false;
26
    if (board[x][y] == '#') return false;
27
    if (board[x][y] != ' ' && board[x][y] != word[pos]) return false;
28
    int newx = x + vertical * inc;
29
    int newy = y + (!vertical) * inc;
30
    return check(board, word, newx, newy, pos + 1, vertical, inc);
31
  }
32

33
  bool valid(vector<vector<char>> &board, int x, int y) {
34
    if (x < 0 || y < 0 || x >= board.size() || y >= board[0].size()) return true;
35
    return board[x][y] == '#';
36
  }
37
};