Repository navigation
Expand file tree
/
Copy pathSurroundRegions.java
More file actions
87 lines (70 loc) · 2.05 KB
/
Copy pathSurroundRegions.java
File metadata and controls
87 lines (70 loc) · 2.05 KB
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
public class SurroundRegions {
public static void main(String[] args) {
char[][] b =
// { { 'X', 'X', 'X', 'X' },
// { 'X', 'O', 'O', 'X' },
// { 'X', 'X', 'O', 'X' },
// { 'X', 'O', 'X', 'X' },
// {'X','X','X','X'}};
{
{'X','O','X','O','X','O'},{'O','X','O','X','O','X'},{'X','O','X','O','X','O'},{'O','X','O','X','O','X'}
};
SurroundRegions r = new SurroundRegions();
r.solve(b);
r.print2D(b);
}
public void solve(char[][] board) {
if (board == null || board.length == 0)
return;
boolean[][] visited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if(board[i][j] == 'O' && !visited[i][j])
depthCheck(i,j,i,j,visited,board);
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if(board[i][j] == '.')
board[i][j] = 'X';
}
}
}
int count = 0;
// 'dfs' -check around
private boolean depthCheck(int ipre, int jpre, int icur, int jcur, boolean[][] visited, char[][] board) {
if(icur == 0 || icur == board.length - 1 || jcur == 0 || jcur == board[0].length -1)
{
visited[icur][jcur] = true;
return false;
}
// visited and X
if(visited[icur][jcur] || board[icur][jcur] == 'X')
{
visited[icur][jcur] = true;
return true;
}
visited[icur][jcur] = true;
boolean t;
t = depthCheck(icur,jcur,icur - 1, jcur, visited, board);
if(!t) return false;
t = t & depthCheck(icur,jcur,icur, jcur + 1, visited, board);
if(!t) return false;
t = t & depthCheck(icur,jcur,icur, jcur - 1, visited, board);
if(!t) return false;
t = t & depthCheck(icur,jcur,icur + 1, jcur, visited, board);
if(!t) return false;
if(board[icur][jcur] == 'O' && t)
board[icur][jcur] = '.';
return t;
}
private void print2D(char[][] table) {
System.out.println("--");
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[0].length; j++) {
System.out.print(table[i][j] + " ");
}
System.out.println();
}
}
}