Can someone tell me how to reduce time in my solution?


  • 0
    A
      // xcomp and ycomp store location of 'O' amd then i cange them to 'X'. 
      class Solution {
        public:
            void solve(vector<vector<char>>& board) {
                vector<int> xcomp, ycomp;
                int r = board.size();
                if(r == 0)    
                    return;`enter code here`
                int c = board[0].size();
                int i, j, x, y, k;
                vector<vector<int>> visited =  vector<vector<int>>(r, vector<int>(c, 0));
               
                for (i = 0; i < r; i++) {
                    for(j = 0; j < c; j++) {
                        visited[i][j] = 0;
                    }
                }
                int x1, y1, m;
                int xmov[] = {1,-1,0,0};
                int ymov[] = {0,0,1,-1};
                int flag= 0;
                for (i = 0; i < r; i++) {
                    for (j = 0; j < c; j++) {
                        if(visited[i][j] == 0 && board[i][j] == 'O') {
                            flag = 0;
                            visited[i][j] = 1;
                            util(board, visited, xmov, ymov, i, j, xcomp, ycomp);
                            for (m = 0; m < xcomp.size(); m++) {
                                if(xcomp[m] == 0 || xcomp[m] == (r-1) || ycomp[m] == 0 || ycomp[m] == (c-1)) {
                                    flag = 1;
                                    break;
                                }
                            }
                            if (flag != 1) {
                                for(m = 0; m < xcomp.size(); m++) {
                                    board[xcomp[m]][ycomp[m]] = 'X';
                                }
                            }
                            xcomp.clear();
                            ycomp.clear();
                         }
                    }
                }
            }
                
                
            
            void util(vector<vector<char>>& board, vector<vector<int>> visited,int xmov[],int ymov[],int i,int j, vector<int> &xcomp, vector<int> &ycomp) {
                int k, x, y;
                
                xcomp.push_back(i);
                ycomp.push_back(j);
                for (k = 0; k < 4; k++) {
                    x = i + xmov[k];
                    y = j + ymov[k];
                    if (x >= 0 && y>=0 && x<board.size() && y<board[0].size()) {
                        if(visited[x][y] == 0 && board[x][y] == 'O') {
                            visited[x][y] = 1;
                            util(board, visited, xmov, ymov, x, y, xcomp, ycomp);
                        }
                    }
                }
            }
        };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.