Планирам да напиша поредица от публикации в блогове с решения за някои проблеми с leetcode. Планирам да участвам в двуседмични контексти и да избирам най-интересните проблеми от там. Днес ще реша задача 2556 от двуседмичен контекст 97. Това беше четвъртият проблем в този контекст, така че се предполага, че е най-трудният. Да преминем към дефинирането на проблема.

Прекъсване на пътя в двоична матрица с най-много едно обръщане.

Дадена ви е 0-индексирана m x n двоична матрица grid. Можете да преминете от клетка (row, col) към всяка от клетките (row + 1, col) или (row, col + 1), която има стойност 1. Матрицата е прекъсната, ако няма път от (0, 0) до (m - 1, n - 1).

Можете да обърнете стойността на най-много една (възможно нито една) клетка. Вие не можете да обръщате клетките (0, 0) и (m - 1, n - 1).

Върнете true ако е възможно матрицата да бъде прекъсната илиfalseв противен случай.

Имайте предвид, че обръщането на клетка променя нейната стойност от 0 на 1 или от 1 на 0.

Пример 1:

Решетката в пример едно е свързана. Можем да изградим следния път от (0,0) до (m-1, n-1)

Но мрежата може да се изключи чрез обръщане на клетка при индекс (1, 2).

Пример 2:

Има 2 различни пътя между (0, 0) и (n-1, m-1)

DFS базирано решение

Интуиция

За да се прекъсне връзката на мрежата с едно премахване, трябва да има клетка в мрежата, която принадлежи на всеки път от (0,0) до (n-1, m-1). В този случай настройката на тази клетка на 0 ще прекъсне всеки път.

Подход

Можем да опитаме да изградим някакъв път от (0, 0) до (n-1, m-1). Можем да използваме DFS (първо търсене в дълбочина), за да направим това. В тази статия няма да навлизам в подробности как работи DFS. Можете да прочетете за DFS тук. Ако не можем да изградим пътя — матрицата вече е прекъсната. Ако сме успели да изградим някакъв път, ние го премахваме от матрицата, като задаваме всяка клетка от пътя, с изключение на краищата, на 0. Следвайки нашата интуиция, ако има клетка в мрежа, която принадлежи на всеки път, тя също принадлежи на намерения път, така че ако го зададем на 0, матрицата трябва да бъде прекъсната. След премахването се опитваме да изградим новия път от (0, 0) до (n-1, m-1). Ако пътят бъде намерен, мрежата не може да бъде прекъсната с едно премахване. Ако не можеше.

Решение

Ще поставя решения на различни езици. За този проблем избрах JavaScript:

var isPossibleToCutPath = function(grid) {
    let n = grid.length;
    let m = grid[0].length
    
    // We will store visited cels in set
    let set = new Set();
    // Add start point to visited.
    set.add(`0_0`);
    // Add start point to path.
    let path = [[0,0]];
    // Possible move directiond down and right.
    let moves = [[0,1], [1,0]];
    
    // DFS implementation
    let dfs = (i, j) => {
        if(i === n-1 && j === m - 1) {
            // We reached bottom right corner - matrix connected.
            return true;
        }
        
        // Generate possible moves from current point
        for (let move of moves) {
            let ni = i + move[0];
            let nj = j + move[1];
            let key = `${ni}_${nj}`
            // Next move should be inside the grid bounds
            // Next move value should be 1. We can only move by 1 cells.
            if( ni < n && nj < m && !set.has(key) && grid[ni][nj] === 1) {
                // Remember next move to not visit it twice.
                set.add(key);
                // Add next move to path
                path.push([ni, nj])
                // Run DFS for next move.
                if(dfs(ni, nj)){
                    // If one of next moves reached the (n-1, m-1) the matrix is connected
                    return true;
                }
                // Current cell is not part of any path. Remove it from path.
                path.pop();
            }
        }
        
        return false;
    }
    
    // Run DFS
    if(!dfs(0, 0)){
        // Initial matrix is already disconnected
        return true;
    }
    
    // Matrix is connected. We have some path.
    path.shift(); // remove [0, 0]
    path.pop(); // remove [n-1, m-1]
    
    // Set every cell of found path to 0
    for (let p of path) {
        grid[p[0]][p[1]] = 0;
    }
    
    // Run DFS for updated matrix once again.
    set = new Set();
    set.add(`0_0`);
    return !dfs(0, 0);
};

Сложност

  • Времева сложност. O(m * n) — в най-лошия случай ще посетим почти всички клетки на мрежата по време на DFS. За този случай не е очевидно, тъй като можем да се движим само надясно и надолу в проблема. Може да изглежда, че трябва да бъде O(m + n), но нека да разгледаме следния пример:

В този случай DFS ще се разпространява по следния начин:

Ще трябва да посетим › (n*m /2) клетки, което е равно на O(n*m) сложност.

  • Сложността на пространството също е O(n*m), тъй като трябва да съхраним всички посетени преди това клетки по време на DFS.

P.S.

„Тук“ е моето решение за този проблем на Leetcode.