This weekend, on a whim, I opened LeetCode to do a question:
https://leetcode-cn.com/problems/number-of-enclaves/
Seeing the question, my first thought is:
Start with the land on the edge and find its largest connected area. Set the marker bit for the found connected area to avoid duplication. After all the connecting areas of marginal land are found, the unmarked land is an enclave.
Finding connected regions is a classical problem of depth first search and breadth first search.
- Identify the starting point on the diagram. Every land on the four sides here is the starting point. Save them to the queue.
- Through depth first search, a connected map of land is constructed.
- Through breadth first search, a connected graph of land is constructed.
Since all eligible land starting points in the queue (land on four sides), all land connectivity graphs can be obtained after traversing to the end.
Depth first search
Start from the starting point and search along an edge until you reach the end point to get a complete edge. Then return to the starting point of the last bifurcation. Search for the next edge. This return to the bifurcation point means using a first in then out stack structure.
Breadth first search
Starting from the starting point, put its adjacent nodes in the queue. Then find the adjacent nodes of these nodes. Until all adjacent nodes are found.
Whether DFS or WFS, in order to ensure that all nodes are searched, search in a fixed order (the node has three child nodes, which are processed from left to right or from right to left).
ArrayDeque in Java
java.util.ArrayDeque can be used as either a stack structure or a queue structure.
ArrayDeque as stack
To implement LIFO (last in first out) stack in Java, it is recommended to use double ended queue on Stack class. The ArrayDeque is faster than the stack class.
ArrayDeque provides the following methods that can be used to implement the stack.
push() - adds an element at the top of the stack
peek() - returns an element from the top of the stack
pop() - returns and removes the element from the top of the stack
ArrayDeque as queue
ArrayDeque is a two ended queue.
Insert an element into a double ended queue
1. Use add(), addFirst() and addLast() to add elements. Full throw exception IllegalStatementException
add() - inserts the specified element into the end of the ArrayDeque two ended queue
addFirst() - insert the specified element at the beginning of the double ended queue
addLast() - insert the specified content at the end of the double ended queue (equivalent to add())
2 use remove(), removeFirst() and removeLast() to return and delete elements. If there is no element that can be deleted, throw an exception, IllegalStatementException. Where remove is equivalent to removeFirst
3 insert elements using offer(), offerFirst() and offerLast(). Offer returns and inserts elements at the end of the queue. If the insertion fails, false is returned.
4 use poll() pollFirst pollLast to delete elements. Poll returns and deletes the first element of the double ended queue. pollFirst is equivalent to poll.
Add and offer insert elements from the end of the queue. In case of failure, add will throw exceptions.
Remove and poll delete elements from the head of the team. In case of failure, remove will throw an exception.
DFS and WFS problem solving
DFS uses ArrayDeque as stack: method offer and poll
WFS uses ArrayDeque as the queue: methods push and pop
(that is, whether the first or last element is taken out.
DFS
package graph.connected_land;
import java.util.ArrayDeque;
public class Dfs {
static class Solution {
int [][] neighbors = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public int numEnclaves(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
ArrayDeque<int[]> searched = new ArrayDeque<int[]>();
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
if (grid[i][0] == 1) {
searched.push(new int[]{i, 0});
visited[i][0] = true;
}
if (grid[i][cols-1] == 1) {
searched.push(new int[]{i, cols-1});
visited[i][cols-1] = true;
}
}
for (int i=1; i < cols-1; i++ ) {
if (grid[0][i] == 1) {
searched.push(new int[]{0, i});
visited[0][i] = true;
}
if (grid[rows-1][i] == 1) {
searched.push(new int[]{rows-1, i});
visited[rows-1][i] = true;
}
}
while(!searched.isEmpty()) {
int[] c = searched.pop();
for (int[] neighbor : neighbors) {
int x = c[0] + neighbor[0];
int y = c[1] + neighbor[1];
System.out.println("x " + x + "y " + y);
if (x < 0 || x > rows-1 || y < 0 || y > cols-1 || visited[x][y] ){
continue;
}
if (grid[x][y] == 1) {
searched.push(new int[]{x, y});
visited[x][y] = true;
}
}
}
int count = 0;
for (int i = 1; i< rows-1; i++) {
for (int j = 1; j < cols-1; j++) {
if (grid[i][j] == 1 && visited[i][j] == false) {
count++;
}
}
}
return count;
}
}
}
WFS
package graph.connected_land;
import java.util.ArrayDeque;
import com.sun.jmx.remote.internal.ArrayQueue;
/*
*/
public class Wfs {
static class Solution {
int [][] neighbors = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public int numEnclaves(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
ArrayDeque<int[]> searched = new ArrayDeque<int[]>();
boolean[][] visited = new boolean[rows][cols];
for (int i = 0; i < rows; i++) {
if (grid[i][0] == 1) {
searched.offer(new int[]{i, 0});
visited[i][0] = true;
}
if (grid[i][cols-1] == 1) {
searched.offer(new int[]{i, cols-1});
visited[i][cols-1] = true;
}
}
for (int i=1; i < cols-1; i++ ) {
if (grid[0][i] == 1) {
searched.offer(new int[]{0, i});
visited[0][i] = true;
}
if (grid[rows-1][i] == 1) {
searched.offer(new int[]{rows-1, i});
visited[rows-1][i] = true;
}
}
while(!searched.isEmpty()) {
int[] c = searched.poll();
for (int[] neighbor : neighbors) {
int x = c[0] + neighbor[0];
int y = c[1] + neighbor[1];
System.out.println("x " + x + "y " + y);
if (x < 0 || x > rows-1 || y < 0 || y > cols-1 || visited[x][y] ){
continue;
}
if (grid[x][y] == 1) {
searched.offer(new int[]{x, y});
visited[x][y] = true;
}
}
}
int count = 0;
for (int i = 1; i< rows-1; i++) {
for (int j = 1; j < cols-1; j++) {
if (grid[i][j] == 1 && visited[i][j] == false) {
count++;
}
}
}
return count;
}
}
}
test data
public static void main(String[] args) {
int[][] grid = {{0,0,0,0},{1,0,1,0},{0,1,1,0},{0,0,0,0}};
int[][] grid2 = {{0,1,1,0},{0,0,1,0},{0,0,1,0},{0,0,0,0}};
int[][] grid3 = {
{0,0,1,1,1,0,1,1,1,0,1},
{1,1,1,1,0,1,0,1,1,0,0},
{0,1,0,1,1,0,0,0,0,1,0},
{1,0,1,1,1,1,1,0,0,0,1},
{0,0,1,0,1,1,0,0,1,0,0},
{1,0,0,1,1,1,0,0,0,1,1},
{0,1,0,1,1,0,0,0,1,0,0},
{0,1,1,0,1,0,1,1,1,0,0},
{1,1,0,1,1,1,0,0,0,0,0},
{1,0,1,1,0,0,0,1,0,0,1}};
Wfs.Solution solution = new Wfs.Solution();
System.out.println(solution.numEnclaves(grid3));
}
link
subject
https://leetcode-cn.com/problems/number-of-enclaves/
The essential difference between depth first search and breadth first search!
https://zhuanlan.zhihu.com/p/74472146
Java ArrayDeque
https://www.cainiaojc.com/java/java-arraydeque.html