Как перемещаться по 2D-массивам в JavaScript?

JSON ответ в JavaScript Программирование и разработка

Двумерный массив или просто двумерный массив — это формат для хранения данных в формате сетки, который представляет собой формат строк и столбцов. В 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 16

Input: 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)

Читайте также:  Различные способы инициализации unordered map в C++
Оцените статью
bestprogrammer.ru
Добавить комментарий