130. 포위된 지역 🚀
솔루션 개발:
질문
이 기사에서는 Leetcode의 '130. Surrounded Regions' 질문을 다룰 것입니다.
의문:
Given an
m x n
matrix board containing'X'
and'O'
, capture all regions that are 4-directionally > surrounded by'X'
.
영역은 둘러싸인 영역에서 모든
'O'
s를 'X'
s로 뒤집음으로써 캡처됩니다.Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
질문 설명
이 질문의 등급은 보통입니다. 대부분 정확합니다. 그러나 이것은 Graph Theory에서 깊이 우선 검색 또는 너비 우선 검색을 잘 이해하고 있는 경우에만 매체입니다. 뿐만 아니라 이러한 아이디어를 매트릭스에 적용하는 방법을 알고 있습니다. 이러한 작업을 수행하는 방법을 모르면 이 문제를 해결하는 데 어려움을 겪을 것입니다.
우리는 행렬을 받았고, 행렬의 가장자리에 접하지 않는 모든 영역을 캡처하라는 지시를 받았습니다.
언뜻 보기에 이 질문은 간단합니다. 깊이 우선 검색을 실행하고 가장자리에 접하는 것이 있는지 확인하세요. 그렇다면 우리는 그 지역이 둘러싸여 있다는 것을 압니다. 그렇지 않은 경우 해당 지역이 둘러싸여 있지 않다는 것을 알 수 있습니다.
권장 지식
우리는 무엇을 알고 있습니까?
어떻게 할 것인가:
우리는 'X'로 둘러쌀 수 없는 모든 잘못된 섬이 행렬의 가장자리에 연결되어 있음을 알고 있습니다. 그래서 먼저, 우리는 주어진 노드 중 하나가 'O'인지 묻는 행렬의 모든 경계를 방문할 것입니다. 그들이 유효하지 않다는 것을 이미 알고 있다면 전체 섬을 'T' 의미로 표시합니다. 온도 나중에 변환을 취소할 것이기 때문입니다.
유효하지 않은 섬을 모두 표시하면 'T'가 아닌 모든 지역을 자동으로 캡처합니다. 모든 임시 영역은 원래 'O' 상태로 다시 변환됩니다.
빅오 표기법:
해결책
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function(board) {
/* -------------------------------------------------------------------------- */
/* 130. Surrounded Regions */
/* -------------------------------------------------------------------------- */
/* ---------------------------- Solution Concept ---------------------------- */
// We need to capture all regions that are not bordered to the edge of the matrix.
// We could perform Depth First Search on all the cells in the matrix and ask
// if any of them border the edge. Instead, we're going to do all the edges
// of the matrix and convert all island that border the island to temp nodes.
// We do this because we already know that the bad nodes border the edge
// of the matrix.
// Once we've marked all the bad islands. We run through the entire matrix
// automatically capturing all the nodes that are not marked as bad. And all
// the previously marked bad nodes are converted to back to islands.
/* ---------------------------- Solution as Code ---------------------------- */
// Matrix Maxes (Makes our life's easier)
const max_rows = board.length - 1;
const max_cols = board[0].length - 1;
// During our search, we can go up, down, left and right.
// We cannot go diagonally! We can only go up, down, left and right.
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
// Our helper depth first function that converts all bad
// islands to marked nodes.
const depth_first_search = (row_index, col_index) => {
// Is it within bounds of the matrix?
// And are we allowed to do dfs on this node?
if (row_index > max_rows || col_index > max_cols || col_index < 0 || row_index < 0 || board[row_index][col_index] != "O"){
return false
}
// So node is within bounds, it bordered the edges of the matrix
// and thus it's a invalid island. As we cannot Surround the Region
// So let's mark it as a 't'. We do this to let us know not to
// convert this node into a 'x'.
board[row_index][col_index] = "T";
// Search in all directions for the rest of the island.
for (const [x, y] of directions){
depth_first_search(row_index + x, col_index + y);
}
}
// let's check all the edges of the matrix checking
// for these bad nodes. If we ever find one, we run
// DFS on it to mark it. Starting with:
// Top and Bottom of matrix
for (let i = 0; i <= max_cols ; i++){
const top = board[0][i];
const bottom = board[max_rows][i];
if (top === "O"){
depth_first_search(0, i);
}
if (bottom === "O"){
depth_first_search(max_rows, i);
}
}
// Left and Right of matrix
for (let i = 0; i <= max_rows ; i++){
const left = board[i][0];
const right = board[i][max_cols];
if (left === "O"){
depth_first_search(i, 0);
}
if (right === "O"){
depth_first_search(i, max_cols);
}
}
// Now we have gone through the entire border of the matrix
// we have now marked all bad islands if their was any.
// Meaning we can automatically capture all regions that
// didn't border that edge.
// We will also unmark all the marked nodes that did border
// the edge of the matrix. We do this because we know that it's an invalid island.
board.forEach((row, row_index) => {
row.forEach((col, col_index) => {
// Capture unmarked regions.
if (col === "O") board[row_index][col_index] = "X"
// Converted marked regions back to a normal island
if (col === "T") board[row_index][col_index] = "O"
})
})
// Return Nothing. We modified our input in place.
};
Reference
이 문제에 관하여(130. 포위된 지역 🚀), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/samuelhinchliffe/130-surrounded-regions-4ll9
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solve = function(board) {
/* -------------------------------------------------------------------------- */
/* 130. Surrounded Regions */
/* -------------------------------------------------------------------------- */
/* ---------------------------- Solution Concept ---------------------------- */
// We need to capture all regions that are not bordered to the edge of the matrix.
// We could perform Depth First Search on all the cells in the matrix and ask
// if any of them border the edge. Instead, we're going to do all the edges
// of the matrix and convert all island that border the island to temp nodes.
// We do this because we already know that the bad nodes border the edge
// of the matrix.
// Once we've marked all the bad islands. We run through the entire matrix
// automatically capturing all the nodes that are not marked as bad. And all
// the previously marked bad nodes are converted to back to islands.
/* ---------------------------- Solution as Code ---------------------------- */
// Matrix Maxes (Makes our life's easier)
const max_rows = board.length - 1;
const max_cols = board[0].length - 1;
// During our search, we can go up, down, left and right.
// We cannot go diagonally! We can only go up, down, left and right.
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
// Our helper depth first function that converts all bad
// islands to marked nodes.
const depth_first_search = (row_index, col_index) => {
// Is it within bounds of the matrix?
// And are we allowed to do dfs on this node?
if (row_index > max_rows || col_index > max_cols || col_index < 0 || row_index < 0 || board[row_index][col_index] != "O"){
return false
}
// So node is within bounds, it bordered the edges of the matrix
// and thus it's a invalid island. As we cannot Surround the Region
// So let's mark it as a 't'. We do this to let us know not to
// convert this node into a 'x'.
board[row_index][col_index] = "T";
// Search in all directions for the rest of the island.
for (const [x, y] of directions){
depth_first_search(row_index + x, col_index + y);
}
}
// let's check all the edges of the matrix checking
// for these bad nodes. If we ever find one, we run
// DFS on it to mark it. Starting with:
// Top and Bottom of matrix
for (let i = 0; i <= max_cols ; i++){
const top = board[0][i];
const bottom = board[max_rows][i];
if (top === "O"){
depth_first_search(0, i);
}
if (bottom === "O"){
depth_first_search(max_rows, i);
}
}
// Left and Right of matrix
for (let i = 0; i <= max_rows ; i++){
const left = board[i][0];
const right = board[i][max_cols];
if (left === "O"){
depth_first_search(i, 0);
}
if (right === "O"){
depth_first_search(i, max_cols);
}
}
// Now we have gone through the entire border of the matrix
// we have now marked all bad islands if their was any.
// Meaning we can automatically capture all regions that
// didn't border that edge.
// We will also unmark all the marked nodes that did border
// the edge of the matrix. We do this because we know that it's an invalid island.
board.forEach((row, row_index) => {
row.forEach((col, col_index) => {
// Capture unmarked regions.
if (col === "O") board[row_index][col_index] = "X"
// Converted marked regions back to a normal island
if (col === "T") board[row_index][col_index] = "O"
})
})
// Return Nothing. We modified our input in place.
};
Reference
이 문제에 관하여(130. 포위된 지역 🚀), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/samuelhinchliffe/130-surrounded-regions-4ll9텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)