Планирам да напиша поредица от публикации в блогове с решения за някои проблеми с 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 различни пътя между (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.