Depth-first search (DFS) topics fall into two types:
-
The search for all nodes is complete
-
Search for a viable solution and end
The difference between the two types of problems lies in the second type of problem: the DFS function uses a Boolean return value to indicate that it has found the answer, and does not proceed once it has found a solution. The return value for the first type of problem is defined according to the problem that the problem requires to be solved.
In fact, the second type of problem is very similar to backtracking. For example, the classic topic “Sudoku” in backtracking algorithm, as long as one solution is feasible in an unfilled box, there is no need to consider other numbers.
Therefore, in the second type of problem framework, after a node is searched, it should be reset to “not searched”, similar to the “undo selection” in the backtracking framework.
Noteworthy points in the framework of the two types of problems are:
- Mark the searched points with the array mark (or other form), search to a point, mark the current point as “searched”
- When calling DFS multiple times, consider whether mark needs to be reset at the end of each call. Resetting is not required for connectivity problems, but is required for finding out whether a path exists, as described below.
Next, the two types of topics are respectively introduced
Type 1: The search for all nodes is complete
The first kind of problem can be summarized as “The problem of finding the size of connected region”.
Find the connected region of a point, and the idea is to start at that point, find the points that connect around you, and then start recursively from those points until there are no points that fit.
Keep looking for… until you run out of points that meet your requirements.
Framework:
mark=[false,false...] // Is used to indicate whether each node has been searched in a round of searchesdefMain function:
forStarting point List: DFS (Starting point)def dfs(The current node) :
ifThe current node is invalid:return;
ifCurrent node searched:return; Marks the current node as searchedforSelection list: DFS (Child nodes)Copy the codeThe waters of the size
The waters of the size
Instead of opening the mark array to mark the searched points, this problem marks them by modifying the current node value.
Both forms have the same purpose. If you do not mark the searched points, you will see StackOverFlow error.
The main thing you need here is to call DFS multiple times, and you don’t need to restore -1 to the original value at the end of each call. Because when two points belong to the same connected region, the result can be obtained by DFS at one point, and the result will be repeated at the other point. As shown below:
class Solution {
int r;
int c;
int[][] land;
int[][] dirs= {{1.0}, {0.1}, {-1.0}, {0, -1}, {-1, -1}, {1.1}, {1, -1}, {-1.1}};
public int[] pondSizes(int[][] land) {
r=land.length;
c=land[0].length;
this.land=land.clone();
List<Integer> res=new ArrayList<> ();
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) {int pondSize=dfs(i,j);
if (pondSize>0) {
res.add(pondSize);
}
}
}
Integer[] ans=res.toArray(new Integer[res.size()]);
Arrays.sort(ans);
int[] fi=new int[res.size()];
for (int i=0; i<ans.length; i++) { fi[i]=ans[i]; }return fi;
}
private int dfs(int x,int y) {
if(! inArea(x, y) || land[x][y]! =0) {
// Contains illegal points (points not in the zone, points not on land) and already searched points (points -1)
return 0;
}
land[x][y]=-1;// it is used to indicate that the current node has been searched
int sum=1;
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1];
sum+=dfs(newX,newY);
}
return sum;
}
private boolean inArea(int x,int y) {
return x>=0 && x<r && y>=0&& y<c; }}Copy the codeminesweeper
minesweeper
class Solution {
int r;
int c;
char[][] board;
int[][] dirs= {{0.1}, {1.0}, {-1.0}, {0, -1}, {1.1}, {-1, -1}, {1, -1}, {-1.1}};
public char[][] updateBoard(char[][] board, int[] click) {
r=board.length;
c=board[0].length;
this.board=board;
dfs(click[0],click[1]);
return board;
}
private void dfs(int x,int y) {
if(! inArea(x, y)) {// Invalid point
return;
}
if (board[x][y]=='M') {// Invalid point
board[x][y]='X';
return;
}
if (board[x][y]=='B' || (board[x][y]>=49 && board[x][y]<=56)) {// The point already searched
return;
}
int count=0;// The number of mines around E
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1];
if (inArea(newX, newY) && board[x+dir[0]][y+dir[1= =]]'M') { count++; }}if(count! =0) {// Mark the current node as a searched point
board[x][y]=(char) (count+48);
}else {
board[x][y]='B';// Mark the current node as a searched point
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1]; dfs(newX,newY); }}}private boolean inArea(int x,int y) {
return x>=0 && x<r && y>=0&& y<c; }}Copy the codeThe number of islands
The number of islands
class Solution {
int r;
int c;
char[][] grid;
int[][] dirs= {{1.0}, {0.1}, {-1.0}, {0, -1}};
public int numIslands(char[][] grid) {
r=grid.length;
if (r==0)
return 0;
c=grid[0].length;
this.grid=grid;
int count=0;
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) {int size=dfs(i,j);
if (size>0) { count++; }}}return count;
}
private int dfs(int x,int y) {
if(! inArea(x, y) || grid[x][y]=='0' || grid[x][y]=='2') {// Invalid points and already searched points
return 0;
}
grid[x][y]='2';// Mark the current node as the searched point
int size=1;// Island size
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1];
size+=dfs(newX,newY);
}
return size;
}
private boolean inArea(int x,int y) {
return x>=0 && x<r && y>=0&& y<c; }}Copy the codeThe number of enclaves
The number of enclaves
Two deep searches:
The first one starts at the boundary point and turns the islands connected to the boundary into the sea. So the rest of the islands are cut off from the border.
The second time, from all the points, calculate the area of each island.
class Solution {
int r;
int c;
int[][] A;
int[][] dirs= {{1.0}, {0.1}, {-1.0}, {0, -1}};
public int numEnclaves(int[][] A) {
r=A.length;
c=A[0].length;
this.A=A.clone();
int res=0;
for (int j=0; j<c; j++) {// process the first line
dfs1(0,j);
}
for (int j=0; j<c; j++) {// Process the last line
dfs1(r-1, j);
}
for (int i=1; i<r-1; i++) {// process the first column
dfs1(i, 0);
}
for (int i=1; i<r-1; i++) {// Process the last column
dfs1(i,c-1);
}
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) { res+=dfs2(i,j); }}return res;
}
private void dfs1(int x,int y) {// Turn enclaves connected to borders into seas
if(! inArea(x, y) || A[x][y]==0) {// Invalid points and searched points (already 0 points)
return;
}
A[x][y]=0;// Mark the current point as the searched point
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1]; dfs1(newX,newY); }}private int dfs2(int x,int y) {// Find the size of each enclave
if(! inArea(x, y) || A[x][y]==0 || A[x][y]==-1) {// Illegal points and searched points (-1)
return 0;
}
A[x][y]=-1;// mark the current point as the searched point
int size=1;
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1];
size+=dfs2(newX,newY);
}
return size;
}
private boolean inArea(int x,int y) {
return x>=0 && x<r && y>=0&& y<c; }}Copy the codeThe largest area of the island
The largest area of the island
class Solution {
int r;
int c;
int[][] grid;
int[][] dirs= {{1.0}, {0.1}, {-1.0}, {0, -1}};
public int maxAreaOfIsland(int[][] grid) {
int maxSize=0;
r=grid.length;
c=grid[0].length;
this.grid=grid;
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) { maxSize=Math.max(maxSize, dfs(i,j)); }}return maxSize;
}
private int dfs(int x,int y) {
if(! inArea(x, y) || grid[x][y]! =1) {// Illegal points and searched points
return 0;
}
grid[x][y]=-1;// Mark the current node as a searched point
int size=1;
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1];
size+=dfs(newX,newY);
}
return size;
}
private boolean inArea(int x,int y) {
return x>=0 && x<r && y>=0&& y<c; }}Copy the codeBorder color
Border color
First DFS finds the connected region where (r0,c0) is located, and then colors its boundary
class Solution {
int r;
int c;
int[][] grid;
int r0;
int c0;
int[][] dirs= {{1.0}, {0.1}, {-1.0}, {0, -1}};
int old;//(r0,c0
public int[][] colorBorder(int[][] grid, int r0, int c0, int color) {
this.grid=grid;
r=grid.length;
c=grid[0].length;
this.r0=r0;
this.c0=c0;
this.old=grid[r0][c0];
dfs(r0,c0);
Queue<int[]> queue=new LinkedList<> ();
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) {if (grid[i][j]==-1) {// Belong to the connected region
for (int[] dir:dirs) {
int newi=i+dir[0];
int newj=j+dir[1];
if(! inArea(newi,newj) || grid[newi][newj]! = -1) {
queue.offer(new int[] {i,j});
break;
}
}
}
}
}
while(! queue.isEmpty()) {// color the border
int[] pos=queue.poll();
grid[pos[0]][pos[1]]=color;
}
for (int i=0; i<r; i++) {// Restore the non-boundary points of the connected region
for (int j=0; j<c; j++) {if (grid[i][j]==-1) { grid[i][j]=old; }}}return grid;
}
private void dfs(int x,int y) {// Find the region where (r0,c0) is located and mark it as -1
if(! inArea(x, y) || grid[x][y]! =old) {// Invalid point
return;
}
if (grid[x][y]==-1) {// The searched point
return;
}
grid[x][y]=-1;// Mark the current node as a searched point
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1]; dfs(newX,newY); }}private boolean inArea(int x,int y) {
return x>=0 && x<r && y>=0&& y<c; }}Copy the codeCount the number of closed islands
Count the number of closed islands
class Solution {
// Find the number of islands that are not connected to the four edges of the grid
int[][] grid;
int r;
int c;
int[][] dirs= {{0.1}, {1.0}, {-1.0}, {0, -1}};
boolean flag=true;// Whether to close
public int closedIsland(int[][] grid) {
r=grid.length;
c=grid[0].length;
// Deep copy of a two-dimensional array
this.grid=new int[r][c];
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) {this.grid[i][j]=grid[i][j]; }}int res=0;
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) {int size=dfs(i,j);
if (size>0 && flag) {
res++;
}
flag=true; }}return res;
}
private int dfs(int x,int y) {
if(! inArea(x, y)) {// Illegal point, indicating not closed
flag=false;
return 0;
}
if(grid[x][y]! =0) {//-1 searched point, 1 water
return 0;
}
grid[x][y]=-1;// Mark the current point as already searched
int size=1;
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1];
size+=dfs(newX,newY);
}
if (flag)
return size;
return 0;
}
private boolean inArea(int x,int y) {
return x>=0 && x<r && y>=0&& y<c; }}Copy the codeCircle of friends
Circle of friends
The connected area here is the circle of friends that X and Y are in
class Solution {
int[][] M;
int r;
int c;
public int findCircleNum(int[][] M) {
this.M=M;
r=M.length;
c=M[0].length;
int res=0;
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) {int count=dfs(i,j);
if (count>0) { res++; }}}return res;
}
private int dfs(int x,int y) {// The number of friends x and y belong to
// Invalid
// Search for
if(M[x][y]! =1) {
return 0;
}
// The flag is searched
M[x][y]=-1;
M[y][x]=-1;
int count=1;
for (int j=0; j<c; j++) {// X is a friend of y, and y's friend is also a friend of X
count+=dfs(y,j);
}
returncount; }}Copy the codeI’m stuck
The first subproblem of this problem, finding the number of squares that can be reached from the initial position S, is type 1 in DFS.
Set an array of R*C to indicate whether S can reach the current node.
AC code:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class Main {
static int r;
static int c;
static char[][] board;
static int[][] lr= {{0.1}, {0, -1}};
static int[][] ud= {{1.0}, {-1.0}};
static int[][] dirs= {{0.1}, {0, -1}, {1.0}, {-1.0}};
static boolean[][] mvTo;
static boolean[][] toEnd;
static boolean[][] mark;// whether this point has already been searched in a round of dfs2
public static void main(String[] args) throws IOException {
Scanner sc=new Scanner(System.in);
r=sc.nextInt();
c=sc.nextInt();
sc.nextLine();
board=new char[r][c];
mvTo=new boolean[r][c];
toEnd=new boolean[r][c];
mark=new boolean[r][c];
for (int i=0; i<r; i++) { board[i]=sc.nextLine().toCharArray(); }int[] start=new int[2];
int[] end=new int[2];
for (int i=0; i<r; i++) {// find the coordinates of S and T
for (int j=0; j<c; j++) {if (board[i][j]=='S') {
start[0]=i;
start[1]=j;
}
if (board[i][j]=='T') {
end[0]=i;
end[1]=j;
}
}
}
dfs1(start[0],start[1]);
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) { toEnd[i][j]=dfs2(i,j,new boolean[r][c]);
mark=new boolean[r][c]; }}int count=0;
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) {if (mvTo[i][j]==true && toEnd[i][j]==false)
count++;
}
}
System.out.println(count);
}
private static void dfs1(int x,int y) {// Can you reach the current point from S
if(! inArea(x, y) || board[x][y]==The '#' || mvTo[x][y]==true)
return;
mvTo[x][y]=true;
if (board[x][y]=='S' || board[x][y]=='+' || board[x][y]=='T') {
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1]; dfs1(newX,newY); }}if (board[x][y]==The '-') {
for (int[] dir:lr) {
int newX=x+dir[0];
int newY=y+dir[1]; dfs1(newX,newY); }}if (board[x][y]=='|') {
for (int[] dir:ud) {
int newX=x+dir[0];
int newY=y+dir[1]; dfs1(newX,newY); }}if (board[x][y]=='. ') {
dfs1(x+1,y); }}private static boolean dfs2(int x,int y,boolean[][] toEnd) {// Can I get to T from the current point
if(! inArea(x, y) || board[x][y]==The '#')// Invalid point
return false;
if (mark[x][y]) {// It has already been searched
return toEnd[x][y];
}
char temp=board[x][y];
if (board[x][y]=='+' || board[x][y]=='S') {
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1];
board[x][y]=The '#';
if (dfs2(newX,newY,toEnd)) {// Go in one direction
mark[x][y]=true;
toEnd[x][y]=true;
board[x][y]=temp;
return true;
}
}
board[x][y]=temp;
mark[x][y]=true;
toEnd[x][y]=false;
return false;
}
if (board[x][y]==The '-') {
for (int[] dir:lr) {
int newX=x+dir[0];
int newY=y+dir[1];
board[x][y]=The '#';
if (dfs2(newX,newY,toEnd)) {
mark[x][y]=true;
toEnd[x][y]=true;
board[x][y]=temp;
return true;
}
}
board[x][y]=temp;
mark[x][y]=true;
toEnd[x][y]=false;
return false;
}
if (board[x][y]=='|') {
for (int[] dir:ud) {
int newX=x+dir[0];
int newY=y+dir[1];
board[x][y]=The '#';
if (dfs2(newX,newY,toEnd)) {
mark[x][y]=true;
toEnd[x][y]=true;
board[x][y]=temp;
return true;
}
}
board[x][y]=temp;
mark[x][y]=true;
toEnd[x][y]=false;
return false;
}
if (board[x][y]=='. ') {
board[x][y]=The '#';
boolean res=dfs2(x+1,y,toEnd);
mark[x][y]=true;
toEnd[x][y]=res;
board[x][y]=temp;
return res;
}
mark[x][y]=true;
toEnd[x][y]=true;
return true;// This point is T
}
private static boolean inArea(int x,int y) {
return x>=0 && x<r && y>=0&& y<c; }}Copy the codeType 2: The search ends after a feasible solution is found
mark=[false,false...] // Is used to indicate whether each node has been searched in a round of searchesdefMain function:
forStarting point list: DFS (starting point) resets markdef dfs(The current node) :
ifThe current node is invalid:return False;
ifCurrent node searched:returnThe result for the current node marks the current node as searchedforSelection list:ifDFS (child node): records the result of the current nodeTrue
return TrueRestore the current node to unsearchedreturn False;
Copy the codePath in matrix
Path in matrix
class Solution {
char[][] board;
String word;
int r;
int c;
int[][] dirs= {{1.0}, {0.1}, {-1.0}, {0, -1}};
boolean[][] mark;
public boolean exist(char[][] board, String word) {
this.board=board;
this.word=word;
r=board.length;
c=board[0].length;
for (int i=0; i<r; i++) {for (int j=0; j<c; j++) { mark=new boolean[r][c];// mark is reset by DFS multiple times
if (dfs(i,j,0)) {
return true; }}}return false;
}
private boolean dfs(int x,int y,int index) {
if (index==word.length()) {
return true;
}
if(! inArea(x, y) || board[x][y]! =word.charAt(index)) {// Invalid point
return false;
}
if (mark[x][y]) {// The searched point
return false;
}
mark[x][y]=true;// mark the current point as searched
for (int[] dir:dirs) {
int newX=x+dir[0];
int newY=y+dir[1];
if (dfs(newX,newY,index+1)) {
return true;
}
}
mark[x][y]=false;// Revert to unsearched
return false;
}
private boolean inArea(int x,int y) {
return x>=0 && x<r && y>=0&& y<c; }}Copy the codeInternode path
Internode path
class Solution {
Map<Integer,Set<Integer>> map=new HashMap<> ();/ / adjacency list
int target;
boolean[] mark;
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
this.mark=new boolean[n+1];
this.target=target;
for (int i=0; i<n; i++) { map.put(i,new HashSet<> ());
}
for (int i=0; i<graph.length; i++) {// Build the adjacency list
int[] edge=graph[i];
Set<Integer> oldSet=map.get(edge[0]);
oldSet.add(edge[1]);
map.put(edge[0],oldSet);
}
return dfs(start);
}
private boolean dfs(int x) {
if (mark[x]) {// Search for
return false;
}
if (x==target) {// The result condition is satisfied
return true;
}
mark[x]=true;// Marks the current node as searched
Set<Integer> nexts=map.get(x);
for (int next:nexts) {
if (dfs(next)) {
return true;
}
}
mark[x]=false;// Restore the current node to unsearched
return false; }}Copy the code