Daily_Java_Programs/Surrounded Regions at main · Sudhipth/Daily_Java_Programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
    int row[]={-1,0,1,0};
    int col[]={0,1,0,-1};
    public void dfs(int rr,int cc,char[][] board,int n,int m,int ans[][])
    {
        ans[rr][cc]=1;
         for(int i=0;i<4;i++)
         {
            int r=rr+row[i];
            int c=cc+col[i];
            if(r>=0 && r<n && c>=0 && c<m && ans[r][c]==0 && board[r][c]=='O')
            dfs(r,c,board,n,m,ans);
         }
    }
    public void solve(char[][] board) {
        int n=board.length;
        int m=board[0].length;
        int ans[][]=new int[n][m];

        for(int i=0;i<m;i++)
        {
            if(board[0][i]=='O')
            {
                ans[0][i]=1;
            dfs(0,i,board,n,m,ans);
            }
        }
        for(int i=0;i<m;i++)
        {
            if(board[n-1][i]=='O')
            {
                 ans[n-1][i]=1;
            dfs(n-1,i,board,n,m,ans);
            }
        }
         for(int i=0;i<n;i++)
        {
            if(board[i][0]=='O')
            {
                 ans[i][0]=1;
            dfs(i,0,board,n,m,ans);
            }
        }
         for(int i=0;i<n;i++)
        {
            if(board[i][m-1]=='O')
            {
                ans[i][m-1]=1;
                dfs(i,m-1,board,n,m,ans);
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(ans[i][j]==0 && board[i][j]=='O')
                {
                    board[i][j]='X';
                }
            }
        }
    }
}