Cho mảng 2D A, mỗi ô là 0 (biển) hoặc 1 (đất). Một nước đi là đi từ ô đất sang ô đất lân cận 4 hướng, hoặc ra khỏi biên lưới. Tìm số ô đất không thể đi ra khỏi biên lưới theo bất kỳ số nước đi nào.
Ví dụ: lưới 4x4 với các ô 1 bị bao quanh bởi 0, kết quả là 3.
Giải pháp dùng DFS:
Mảng hướng dir = [[1,0],[-1,0],[0,1],[0,-1]]
Hàm dfs(x, y, A): nếu ngoài biên hoặc A[x][y]==0 thì return; đặt A[x][y]=0; gọi đệ quy 4 hướng
Từ main: duyệt các ô trên biên (hàng 0, hàng n-1, cột 0, cột m-1), nếu là 1 thì gọi dfs để xóa toàn bộ vùng đất liên thông với biên
Đếm các ô 1 còn lại trong lưới
Ví dụ
#include <bits/stdc++.h> using namespace std; int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; class Solution { public: void dfs(int x, int y, vector < vector <int>>& A){ if(x < 0 || y < 0 || x >= A.size() || y >= A[0].size() || A[x][y] == 0) return; A[x][y] = 0; for(int k = 0; k < 4; k++){ int nx = dir[k][0] + x; int ny = dir[k][1] + y; dfs(nx, ny, A); } } int numEnclaves(vector<vector<int>>& A) { int ret = 0; int n = A.size(); int m = n ? A[0].size() : 0; for(int i = 0; i < n; i++){ if(A[i][0] == 1) dfs(i, 0, A); if(A[i][m - 1] == 1) dfs(i, m - 1, A); } for(int i = 0; i < m; i++){ if(A[0][i] == 1) dfs(0, i, A); if(A[n - 1][i] == 1) dfs(n - 1, i, A); } for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ ret += A[i][j]; } } return ret; } }; int main(){ vector<vector<int>> v1 = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}}; Solution ob; cout << (ob.numEnclaves(v1)); }Đầu vào
[[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Đầu ra
3