# Easy Understand Strightforward Java DP Solution with Explanation

• The basic idea is to build a boolean matrix initialized with false, which means all points are not connected to open. And then scan the board, once an 'O' is found, check whether it is on the boarder, if so, change its boolean value to be true, if not, check its surroundings, if any of them is true, it's true. Keep scanning and updating the DP matrix first from left-top then from right-bottom. Mostly, one pair of scans is enough, but actually some special cases need a second pair. So, define a boolean variable to check whether a change is made or not in the scan. If none change, break and our DP matrix is correctly built.
After that, scan the board, when come across an 'O', check the DP matrix, if it says false, change it to 'X';

``````public void solve(char[][] board) {

int height = board.length;
if (height < 1)
return;

int width = board[0].length;

boolean[][] dp = new boolean[height][width];

//Start scanning twice as one pair
while (true) {
boolean changed = false;

//Scan from top-left
for (int i = 0; i < height; i++)
for (int j = 0; j < width; j++) {
if (board[i][j] == 'O') {
boolean temp = dp[i][j];
dp[i][j] = dp[i][j] || i == 0 || i == height - 1
|| j == 0 || j == width - 1 || dp[i - 1][j]
|| dp[i][j - 1] || dp[i + 1][j] || dp[i][j + 1];

changed = changed || !(temp == dp[i][j]);
}
}

//Scan from bottom-right
for (int i = height - 1; i >= 0; i--)
for (int j = width - 1; j >= 0; j--) {
if (board[i][j] == 'O') {
boolean temp = dp[i][j];
dp[i][j] = dp[i][j] || i == 0 || i == height - 1
|| j == 0 || j == width - 1 || dp[i - 1][j]
|| dp[i][j - 1] || dp[i + 1][j] || dp[i][j + 1];
changed = changed || !(temp == dp[i][j]);
}
}

///DP matrix is done!
if (!changed)
break;
}

//Change O to X according to DP matrix
for (int i = height - 1; i >= 0; i--)
for (int j = width - 1; j >= 0; j--)
if (board[i][j] == 'O' && dp[i][j] == false)
board[i][j] = 'X';

}``````

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