Battleships in a Board LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool isSafe(int i, int j, int r, int c, vector<vector<char>> &arr,
4
              vector<vector<bool>> &visited) {
5
    if (i < 0 || i > r || j < 0 || j > c) {
6
      return false;
7
    }
8
    //  cout<<arr[i][j]<<" ";
9
    if (arr[i][j] != 'X') {
10
      return false;
11
    }
12
    if (arr[i][j] == 'X' && visited[i][j] == true) {
13
      return false;
14
    }
15

16
    if (arr[i][j] == 'X' && visited[i][j] == false) {
17
      return true;
18
    }
19
    return false;
20
  }
21

22
  void solve(vector<vector<char>> &arr, vector<vector<bool>> &visited, int &r, int &c, int i,
23
             int j) {
24
    if ((i > r && j > c) && (i < 0 && j < 0)) {
25
      return;
26
    }
27

28
    // down (i+1,j)
29
    if (isSafe(i + 1, j, r, c, arr, visited)) {
30
      visited[i + 1][j] = true;
31
      solve(arr, visited, r, c, i + 1, j);
32
    } else {
33
      // if(arr[i][j] == 'X'){
34
      //      visited[i][j] = true;
35
      // }
36
    }
37
    // // right (i,j+1)
38

39
    if (isSafe(i, j + 1, r, c, arr, visited)) {
40
      visited[i][j + 1] = true;
41
      solve(arr, visited, r, c, i, j + 1);
42
    } else {
43
      // if(arr[i][j] == 'X'){
44
      //      visited[i][j] = true;
45
      // }
46
    }
47
    // left (i,j-1);
48
    if (isSafe(i, j - 1, r, c, arr, visited)) {
49
      visited[i][j - 1] = true;
50
      solve(arr, visited, r, c, i, j - 1);
51
    } else {
52
      // if(arr[i][j] == 'X'){
53
      //      visited[i][j] = true;
54
      // }
55
    }
56
    // up   (i-1,j)
57
    if (isSafe(i - 1, j, r, c, arr, visited)) {
58
      visited[i - 1][j] = true;
59
      solve(arr, visited, r, c, i - 1, j);
60
    } else {
61
      // if(arr[i][j] == 'X'){
62
      //      visited[i][j] = true;
63
      // }
64
    }
65
  }
66
  int countBattleships(vector<vector<char>> &board) {
67
    int row = board.size() - 1;
68
    int col = board[0].size() - 1;
69
    vector<vector<bool>> isVisited(row + 1, vector<bool>(col + 1, false));
70
    vector<vector<int>> toStart;
71
    for (int i = 0; i < board.size(); i++) {
72
      for (int j = 0; j < board[i].size(); j++) {
73
        if (board[i][j] == 'X') {
74
          vector<int> temp(2);
75
          temp[0] = i;
76
          temp[1] = j;
77
          //  cout<<i<<" "<<j<<endl;
78
          toStart.push_back(temp);
79
        }
80
      }
81
    }
82
    int ans = 0;
83
    for (int i = 0; i < toStart.size(); i++) {
84
      if (isVisited[toStart[i][0]][toStart[i][1]]) {
85
      } else {
86
        isVisited[toStart[i][0]][toStart[i][1]] = true;
87
        solve(board, isVisited, row, col, toStart[i][0], toStart[i][1]);
88
        ans++;
89
      }
90
    }
91

92
    //  for(auto cc:isVisited){
93
    //      for(auto c:cc){
94
    //          cout<<c<<" ";
95
    //      }
96
    //      cout<<endl;
97
    //  }
98

99
    return ans;
100
  }
101
};