define

Depth-first Search (DFS) and Breadth First Search (BFS) are the basic violence techniques, which are often used in traversal problems of trees and graphs.

  1. DFS: Start at the starting point and walk as far as you can until you can no longer walk, then back up, go the other way, and continue down until you have accessed all the nodes. This method is DFS, this is the stack (recursion);
  2. BFS: Start at the beginning, go around, and continue around. The basic idea is to access the nodes already visited first. This is the implementation of the queue.

The illustration

BFS and DFS logarithms are used for traversal, and the access order of nodes.

DFS sample

Give a two-dimensional matrix to represent the maze (0 can go, 1 can not go), give the initial position, judge whether the maze can be solved.

int a[N][N]/ / a maze
int bx,by;// Start coordinates
int n,m;// Matrix n*m
int dx[4] = {- 1.0.1.0},dy[4] = {0.1.0.- 1};// Go up, right, down, left
bool dfs(int x,int y)
{
	if(x<0||y<0||x>=n||y>=m) return true;// If out of range, return can walk out
	a[x][y]=1;// Set traversal to 1.
	for(int i=0; i<4; i++) {int cx=x+dx[i],cy=y+dy[i];
		if(a[cx][cy]==0)// If you can, proceed to the next step
		{
			if(dfs(cx,cy)) return true;// If true is returned, true is returned;}}return false;	
} 
Copy the code

BFS sample

Give a two-dimensional matrix representing the maze (0 possible, 1 impossible), give the initial position, and calculate the minimum number of steps you can take to get out of the maze.

int a[N][N]/ / a maze
int bx,by;// Start coordinates
int n,m;// Matrix n*m
int dx[4] = {- 1.0.1.0},dy[4] = {0.1.0.- 1};// Go up, right, down, left
int BFS(a)
{
	queue<pair<pair<int.int>,int>> q;// One saves the position and one saves the number of steps to the current position;
	q.push({{bx,by},0});
	a[bx][by]=1;
	while(! q.empty())
	{
		auto t=q.front(a); q.pop(a);// Remove the enemy element
		int x=t.first.first,y=t.first.second;
		int step=q.second;
		for(int i=0; i<4; i++) {int cx=x+dx[i],cy=y+dy[i];
			if(x<0||y<0||x>=n||y>=m) return step+1;// If out of range, return the number of steps directly;
			if(a[cx][cy]==0)// If you can go, put its coordinates into the queue
			{
				q.push({{cx,cy},step+1});  
				a[cx][cy]=1;// Set the current position to 1 to indicate that it has been passed}}}}Copy the code