Двумерный массив или просто двумерный массив — это формат для хранения данных в формате сетки, который представляет собой формат строк и столбцов. В JavaScript нет специального способа объявления 2D-массива, мы можем просто передать массив как элемент внутри другого массива. массив, полученный этим методом, будет создан как двумерный массив.
Синтаксис:
var arr = [[…], […], …]
Примеры:
Input: grid = [[1, 2, 3, 4 ], [5, 6, 7, 8 ], [9, 10, 11, 12 ], [13, 14, 15, 16 ] ]
Output: 1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16Input: grid = [ [ -1, 2, 3 ], [ 0, 9, 8 ], [ 1, 0, 1 ] ]
Output: -1 2 3 8 1 0 9 0 1
Обход 2D-массива
В общем, есть два способа обхода двумерного массива. Два метода:
- Обход BFS (поиск в ширину)
- Обход DFS (поиск в глубину)
Подход 1: Чтобы решить проблему с помощью обхода BFS, выполните следующие шаги:
Обход BFS также называется обходом порядка уровней, и для его реализации мы используем структуру данных очереди. В этом алгоритме сначала просматриваются все узлы одного уровня и дочерние узлы.
- Выполните следующие шаги, чтобы решить проблему:
- Выберите корневой узел и инициализируйте очередь
- Отметьте посещенный узел, распечатайте его, а затем поместите в очередь.
- Инициализировать 2D-массив, чтобы пометить посещенные ячейки и пометить корневой узел как посещенный.
- Теперь итерируйте, пока очередь не станет пустой, и выполните следующие шаги:
- Удалите из очереди текущую ячейку, присутствующую в начале, и распечатайте ее.
- Посетите соседние ячейки
- Отметьте их как посещенные, распечатайте и поставьте их в очередь
Ниже приведена реализация вышеуказанного подхода:
Javascript
// Javascript program for the above approach var ROW = 4; var COL = 4; // Direction vectors var dRow = [-1, 0, 1, 0 ]; var dCol = [0, 1, 0, -1 ]; // Function to check if a cell // is be visited or not function isValid(vis, row, col) { // If cell lies out of bounds if (row < 0 || col < 0 || row >= ROW || col >= COL) return false; // If cell is already visited if (vis[row][col]) return false; // Otherwise return true; } // Function to perform the BFS traversal function BFS( grid, vis, row, col) { // Stores indices of the matrix cells var q = []; // Mark the starting cell as visited // and push it into the queue q.push([row, col ]); vis[row][col] = true; // Iterate while the queue // is not empty while (q.length!=0) { var cell = q[0]; var x = cell[0]; var y = cell[1]; console.log( grid[x][y] + " "); q.shift(); // Go to the adjacent cells for (var i = 0; i < 4; i++) { var adjx = x + dRow[i]; var adjy = y + dCol[i]; if (isValid(vis, adjx, adjy)) { q.push([adjx, adjy ]); vis[adjx][adjy] = true; } } } } // Driver Code // Given input matrix var grid = [[1, 2, 3, 4 ], [5, 6, 7, 8 ], [9, 10, 11, 12 ], [13, 14, 15, 16 ] ]; // Declare the visited array var vis = Array.from(Array(ROW), ()=> Array(COL).fill(false)); BFS(grid, vis, 0, 0);
Выход
1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16
Временная сложность: O(N * M)
Вспомогательное пространство: O(N * M)
Подход 2. Чтобы решить проблему с помощью обхода DFS, следуйте следующей идее:
Обход DFS — это алгоритм, который использует структуру данных стека для реализации принципа LIFO (Last In First Out). В этом алгоритме мы сначала выберем метку узла, которую он посетил, и посетим все его дочерние узлы. Как только дочерний узел не останется, мы будем использовать возврат для посещения непосещенных узлов.
Следуйте инструкциям, чтобы решить проблему:
- Выберите корневой узел и инициализируйте стек.
- Отметьте посещенный узел, распечатайте его, а затем поместите в стек.
- Инициализируйте 2D-массив, чтобы отметить посещенные ячейки и пометить корневой узел как посещенный.
- Теперь итерируйте, пока очередь не станет пустой, и выполните следующие шаги:
- Вставьте элемент в верхнюю часть стека и распечатайте его.
- Вставьте соседние ячейки в стек.
Ниже приведена реализация вышеуказанного подхода:
Javascript
// Javascript program of the above approach
var ROW = 3;
var COL = 3
// Initialize direction vectors
var dRow = [0, 1, 0, -1];
var dCol = [ -1, 0, 1, 0];
// Function to check if mat[row][col]
// is unvisited and lies within the
// boundary of the given matrix
function isValid(vis, row, col)
{
// If cell is out of bounds
if (row < 0 || col < 0
|| row >= ROW || col >= COL)
return false;
// If the cell is already visited
if (vis[row][col])
return false;
// Otherwise, it can be visited
return true;
}
// Function to perform DFS
// Traversal on the matrix grid[]
function DFS(row, col, grid, vis)
{
// Initialize a stack of pairs and
// push the starting cell into it
var st = [];
st.push([ row, col ]);
// Iterate until the
// stack is not empty
while (st.length!=0) {
// Pop the top pair
var curr = st[st.length-1];
st.pop();
var row = curr[0];
var col = curr[1];
// Check if the current popped
// cell is a valid cell or not
if (!isValid(vis, row, col))
continue;
// Mark the current
// cell as visited
vis[row][col] = true;
// Print the element at
// the current top cell
console.log( grid[row][col] + " ");
// Push all the adjacent cells
for (var i = 0; i < 4; i++) {
var adjx = row + dRow[i];
var adjy = col + dCol[i];
st.push([ adjx, adjy ]);
}
}
}
// Driver Code
var grid = [ [ -1, 2, 3 ],
[ 0, 9, 8 ],
[ 1, 0, 1 ] ];
// Stores whether the current
// cell is visited or not
var vis = Array.from(Array(ROW), ()=> Array(COL).fill(false));
// Function call
DFS(0, 0, grid, vis); Выход
-1 2 3 8 1 0 9 0 1
Временная сложность: O(N * M)
Вспомогательное пространство: O(N * M)
