My 12ms dfs c++


  • 2
    F
        class Solution {
    public:
        void solve(vector<vector<char>>& board) {
            int rows = board.size();
            if(rows==0)
                return;
            int cols = board[0].size();
            for(int i=0;i<rows;i++){
                if(board[i][0]=='O'){
                    dfs(board,i,0);
                }
                if(board[i][cols-1]=='O')
                    dfs(board,i,cols-1);
            }
            for(int j=0;j<cols;j++){
                if(board[0][j]=='O')
                    dfs(board,0,j);
                if(board[rows-1][j]=='O')
                    dfs(board,rows-1,j);
            }
            for(int i=0;i<rows;i++){
                for(int j=0;j<cols;j++){
                    if(board[i][j]=='Y')
                        board[i][j]='O';
                    else
                        board[i][j]='X';
                }
            }
        }
        void dfs(vector<vector<char>>& board, int x, int y){
            int rows = board.size();
            int cols = board[0].size();
            board[x][y]='Y';
           // cout<<x<<" "<<y<<endl;
            int dir[4][2] = {0,1,1,0,0,-1,-1,0};
            for(int i=0;i<4;i++){
                int tx = x+dir[i][0];
                int ty = y+dir[i][1];
                while(tx>=0&&tx<rows&&ty>=0&&ty<cols&&board[tx][ty]=='O'){
                    board[tx][ty]='Y';
                    //cout<<tx<<" "<<ty<<endl;
                    for(int k=1;k<=3;k+=2){
                        int px = tx+dir[(i+k)%4][0];
                        int py = ty+dir[(i+k)%4][1];
                        if(px>=0&&px<rows&&py>=0&&py<cols&&board[px][py]=='O')dfs(board,px,py);
                        
                    }
                    tx = tx+dir[i][0];
                    ty = ty+dir[i][1];
                }
            }
        }
    };

Log in to reply
 

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