Giả sử chúng ta có một lưới 2D các giá trị nhị phân (0 và 1), chúng ta thay đổi tối đa một 0 thành 1. Sau đó, chúng ta phải tìm kích thước của đảo lớn nhất? Ở đây đảo là một nhóm các 1 kết nối theo 4 hướng (trên, dưới, trái, phải).
Vì vậy, nếu đầu vào là [[1, 0], [0, 1]], thì đầu ra sẽ là 3, vì nếu chúng ta thay một 0 thành 1 và kết nối hai 1, thì chúng ta sẽ có một đảo với diện tích = 3.
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau −
Định nghĩa mảng dir kích thước: 4 x 2, dir := {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
Định nghĩa hàm dfs(), nhận idx, i, j, lưới,
nếu (i,j) nằm trong vùng lưới và grid[i, j] khác 1, thì −
trả về 0
ret := 1
grid[i, j] := idx
for khởi tạo k := 0, khi k < 4, cập nhật (tăng k lên 1), thực hiện −
ni := dir[k, 0] + i, nj := dir[k, 1] + j
ret := ret + dfs(grid, ni, nj, idx)
trả về ret
Từ phương thức main, thực hiện như sau −
ret := 0, idx := 2
Định nghĩa mảng area kích thước 2
n := số hàng của lưới, m := số cột của lưới
for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), thực hiện −
for khởi tạo j := 0, khi j < m, cập nhật (tăng j lên 1), thực hiện −
nếu grid[i, j] bằng 1, thì −
chèn dfs(grid, i, j, idx) vào cuối area
ret := max của ret và phần tử cuối của area
(tăng idx lên 1)
for khởi tạo i := 0, khi i < n, cập nhật (tăng i lên 1), thực hiện −
nếu grid[i, j] bằng 0, thì −
Định nghĩa một tập hợp idxs
for khởi tạo k := 0, khi k < 4, cập nhật (tăng k lên 1), thực hiện −
ni := i + dir[k, 0], nj := j + dir[k, 1]
nếu ni,nj trong phạm vi lưới, thì −
nếu grid[ni, nj] khác 0, thì −
chèn grid[ni, nj] vào idxs
temp := 1
cho tất cả phần tử it trong idxs, thực hiện −
temp := temp + area[it]
(tăng it lên 1)p + area[it]
ret := max của ret và temp
trả về ret
Hãy xem triển khai sau để hiểu rõ hơn −
Ví dụ
#include <bits/stdc++.h> using namespace std; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; class Solution { public: int dfs(vector < vector <int> >& grid, int i, int j, int idx){ if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1) return 0; int ret = 1; grid[i][j] = idx; for(int k = 0; k < 4; k++){ int ni = dir[k][0] + i; int nj = dir[k][1] + j; ret += dfs(grid, ni, nj, idx); } return ret; } int largestIsland(vector<vector<int>>& grid) { int ret = 0; int idx = 2; vector <int > area(2); int n = grid.size(); int m = grid[0].size(); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(grid[i][j] == 1){ area.push_back(dfs(grid, i, j, idx)); ret = max(ret, area.back()); idx++; } } } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(grid[i][j] == 0){ set <int> idxs; for(int k = 0; k < 4; k++){ int ni = i + dir[k][0]; int nj = j + dir[k][1]; if(ni < 0 || nj < 0 || ni >= grid.size() || nj >= grid[0].size()) continue; if(grid[ni][nj]){ idxs.insert(grid[ni][nj]); } } int temp = 1; set <int> :: iterator it = idxs.begin(); while(it != idxs.end()){ temp += area[*it]; it++; } ret = max(ret, temp); } } } return ret; } }; main(){ Solution ob; vector<vector<int>> v = {{1,0},{0,1}}; cout << (ob.largestIsland(v)); } Đầu vào
{{1,0},{0,1}} Đầu ra
3