Search DFS and BFS

dfs And backtracking algorithm

dfs The difference between enumeration and violence is ： Violence enumeration is to enumerate every situation , Whether the situation is reasonable or not . and dfs It is an optimization algorithm under violent enumeration , It will remove some unqualified conditions .（ prune ）

dfs Templates

dfs It is essentially a recursive tree , And depth first traversal .
So the core is to fill in the blanks of each branch

void dfs(int k)
{
    
	if( A branch ends ）
	{
    
		 Determine the optimal solution / Record answer ;// Judging the optimal solution is similar to res = max(res,a)
		return;
	}
	for( Enumerate the options that can be filled in this layer ）
	{
    
		if( This option is reasonable )
		{
    
			 Fill in the ;
			dfs(k+1);// Go to the next floor 
			 Restore the scene ;
		}
	}
}

Fourth order Sudoku

Write a program to see how to fill in the fourth-order Sudoku .
Examination site ：dfs

Be careful ：
1. Subscript of one-dimensional array （ from 1 Start ） Turn it into a two-dimensional array row Formula for ：

row = (x - 1) / n + 1;//n Is the length of the two-dimensional array 

2. Subscript of one-dimensional array （ from 1 Start ） Turn it into a two-dimensional array col Formula for ：

col = (x - 1) % n + 1;//n Is the length of the two-dimensional array 

3. Block subscript

block = (row - 1) / 2 * 2 + (col - 1) / 2 + 1

4.dfs It is the most difficult to judge whether this void is legal . You can imitate this format , Use an array to record whether it is legal .
5. Although the fourth-order Sudoku in the title gives us the feeling that it is a two-dimensional array , But creating a one-dimensional array is better . It is universal

#include <iostream>

using namespace std;

int board[25];
int r[5][5], c[5][5], b[5][5];
int ans;
void dfs(int x)
{
    
	if (x > 16)
	{
    
		ans++;
		// Output all schemes 
		/*for (int i = 1; i <= 16; i++) { cout << board[i]; if (i % 4 == 0) puts(""); } puts("");*/
		return;
	}
	int row = (x - 1) / 4 + 1;
	int col = (x - 1) % 4 + 1;
	int block = (row - 1) / 2 * 2 + (col - 1) / 2 + 1;
	for (int i = 1; i <= 4; i++)
	{
    
		if (r[row][i] == 0 && c[col][i] == 0 && b[block][i] == 0)
		{
    
			board[x] = i;
			r[row][i] = 1;  c[col][i] = 1; b[block] [i] = 1;
			dfs(x + 1);
			r[row][i] = c[col][i] = b[block][i] = 0;
		}
	}
}

int main()
{
    
	dfs(1);
	cout << ans;
}

8 Queen

Examination site ：dfs
notes ：
1. The diagonal judgment method can use a one-dimensional array to judge whether there are chess pieces on the diagonal . A positive diagonal , A sub diagonal

2. Print a two-dimensional character array , It can be used puts To print , Each row of a two-dimensional array is actually equivalent to a string ,puts It can be printed directly . And finally add a new line .

Code ：

#include <iostream>
#include <cstring>

using namespace std;

char board[10][10];
int col[100], dg[100], udg[100];
int ans;

void dfs(int k)
{
    
	if (k == 8)
	{
    
		/*for (int i = 0; i < 8; i++) puts(board[i]); puts("");*/
		ans++;
		return;
	}

	for (int i = 0; i < 8; i++)
	{
    
		if (col[i] == 0 && dg[i + k] == 0 && udg[i - k + 8] == 0)
		{
    
			board[k][i] = '*';
			col[i] = dg[i + k] = udg[i - k + 8] = 1;
			dfs(k + 1);
			col[i] = dg[i + k] = udg[i - k + 8] = 0;
			board[k][i] = '#';
		}
	}
}

int main()
{
    
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			board[i][j] = '#';
	dfs(0);
	cout << ans;
}

bfs

bfs Templates

This is one of the templates , It can be used size Process the contents of the same layer together .

bool vis[];
queue<typename> q;
q.push( First element )

while(!q.empty())
{
    
	int sz = q.size();// The size of each layer 
	for(int i = 0; i < sz; i++)
	{
    
		int t = q.front();
		q.pop();
		if(t ==  The goal is ) return  Minimum steps or something 
		for( Elements  ： t The elements around )
		{
    
			if( Meet certain conditions  && vis[t] == false)
				q.push( Elements );
				vis[ Elements ] = true;
		}
	}
	step++;// Number of steps to maintain ++
}

This is the second template ,state You can use a structure to manage , Like above step It is usually a member of this structure .

q.push( The initial state );
while(!q.empty())
	state u = q.front();
	q.pop();
	for( All states that can be extended next to the first state )
		if(isvalid())
			q.push(v);

The traversal of the horse

There is one n×m The chessboard of , There is a horse at some point , Calculate how many steps the horse must take to reach any point on the chessboard .
The traversal of the horse
Examination site ：bfs
The template questions .
stay bfs The number of maintenance steps in the template .
The relationship between steps is as follows ：

 Current steps  =  Last steps  + 1

ac Code ：

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int N = 410;
int g[N][N];
queue<pair<int, int> > q;
int dir[8][2] = {
     {
    2,1},{
    1,2},{
    -1,2},{
    -2,1},{
    -2,-1},{
    -1,-2},{
    1,-2},{
    2,-1}};
bool vis[N][N];
int step = 1;

void bfs(int n, int m, int x, int y)
{
    
	q.push({
     x,y });
	vis[x][y] = true;
	g[x][y] = 0;
	while (!q.empty())
	{
    	
		int sz = q.size();
		for (int i = 0; i < sz; i++)
		{
    
			int x = q.front().first, y = q.front().second;
			q.pop();
			for (int i = 0; i < 8; i++)
			{
    
				int newx = x + dir[i][0], newy = y + dir[i][1];
				if (newx >= 0 && newy >= 0 && newx < n && newy < m && vis[newx][newy] == false)
				{
    
					q.push({
     newx,newy });
					g[newx][newy] = step;
					vis[newx][newy] = true;
				}
			}
		}
		step++;
	}
}

int main()
{
    
	int n, m, x, y;
	cin >> n >> m >> x >> y;
	x--, y--;
	memset(g, -1, sizeof(g));
	bfs(n, m, x, y);
	for (int i = 0; i < n; i++)
	{
    
		for (int j = 0; j < m; j++)
			printf("%-5d", g[i][j]);
		puts("");
	}
}

Strange elevator

Strange elevator

Examination site bfs
notes ： Learn to use structures to manage some information , It will be clearer .

Use template 1 To manage the number of button presses

#include <iostream>
#include <queue>

using namespace std;
const int N = 210;
int n, a, b;
int f[N];
int ans;
queue<int> q;
bool vis[N];

int dir[2] = {
     1,-1 };

int bfs(int a, int b)
{
    
	q.push(a);
	while (!q.empty())
	{
    
		int sz = q.size();
		for (int i = 0; i < sz; i++)
		{
    
			int t = q.front();
			q.pop();
			if (t == b) return ans;
			for (int i = 0; i < 2; i++)
			{
    
				int opt = t + f[t - 1] * dir[i];
				if (opt >= 1 && opt <= b && vis[opt] == false)
				{
    
					q.push(opt);
					vis[opt] = true;
				}
			}
		}
		ans++;
	}
	return -1;
}

int main()
{
    
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) cin >> f[i];
	cout << bfs(a, b);
}

Use template 2 To manage the number of button presses

#include <iostream>
#include <queue>

using namespace std;
const int N = 210;
int n, a, b;
int f[N];
int ans;
bool vis[N];

int dir[2] = {
     1,-1};
struct node {
     int floor; int d; };
queue<node> q;

int bfs(int a, int b)
{
    
	q.push({
     a,0 });
	while (!q.empty())
	{
    
		int floor = q.front().floor;
		int d = q.front().d;
		q.pop();
		if (floor == b) return d;
		for (int i = 0; i < 2; i++)
		{
    
			int opt = floor + f[floor - 1] * dir[i];
			if (opt >= 1 && opt <= b && vis[opt] == false)
			{
    
				q.push({
     opt,d + 1 });
				vis[opt] = true;
			}
		}
	}
	return -1;
}

int main()
{
    
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) cin >> f[i];
	cout << bfs(a, b);
}

meteor shower

Meteor Shower S
This topic looks very complicated , Because in bfs The concept of time is introduced in the . So the template 1 That kind of formal writing is not easy to write , It is much more convenient to describe it with a structure .

notes ：
1. The limiting condition for the expansion of this problem is ：

 Time to get to this grid  <  The time of the explosion  - 1 
 as a result of ： It takes a second to get to the next grid 

2. To initialize a death Array , It is used to record the explosion time of each grid , When recording , Because they may affect each other , So use

death[x][y] = min(death[x][y], time);

ac Code ：

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;
const int N = 50010, M = 310;
int g[M][M], death[M][M];
bool vis[M][M];

int dir[4][2] = {
     {
    1,0}, {
    -1,0},{
    0,1},{
    0,-1} };

struct node
{
    
	int x;
	int y;
	int t;
}Node[N];

queue<node> q;

int bfs()
{
    
	q.push({
     0,0,0 });
	vis[0][0] = true;

	while (!q.empty())
	{
    
		node tmp = q.front();
		int x = tmp.x, y = tmp.y, t = tmp.t;
		q.pop();
		if (death[x][y] == 0x7f7f7f7f) return t;
		for (int i = 0; i < 4; i++)
		{
    
			int newx = x + dir[i][0], newy = y + dir[i][1];
			if (newx >= 0 && newy <= 300 && newy >= 0 && newy <= 300 && vis[newx][newy] == false && (tmp.t < death[newx][newy] - 1))
			{
    
				q.push({
     newx,newy,t + 1 });
				vis[newx][newy] = true;
			}
		}
	}
	return -1;
}

int main()
{
    
	memset(death, 0x7f, sizeof death);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
    
		int x, y, t;
		cin >> x >> y >> t;
		Node[i] = {
     x, y , t };
		death[x][y] = min(t, death[x][y]);
		for (int i = 0; i < 4; i++)
		{
    
			int newx = x + dir[i][0], newy = y + dir[i][1];
			if (newx >= 0 && newx <= 300 && newy >= 0 && newy <= 300) death[newx][newy] = min(death[newx][newy], t);
		}
	}

	cout << bfs();
}