I mainly read more than 50 blogs this week. Because of offline reasons, I have less time to read questions and less practice to learn knowledge. Because I have a deeper understanding of operator overloading in stl in my usual program class. This week is also a summary of the deep search topic

································································································································

p1451 calculate the number of cells

The difference of this topic is that we need to consider whether the top, bottom, left and right of cell numbers are cell numbers. The processing method is similar to the block knowledge written last week, that is, define dx and dy to judge the surrounding of cell numbers, and start the search as a coordinate system. See whether the searched elements meet the boundary conditions or are in a legal state. If not, change to the next direction, otherwise mark it. Every time a connected block is searched, we record the number of blocks, and then search for the next block. For such problems, marking is particularly important, and the backtracking process is much more important than others.

int dx[4]={0,0,1,-1};//Four direction array
int dy[4]={1,-1,0,0};//Four direction array
vis[100][100]={0}
void dfs(int x, int y, int end_x, int end_y, int geshu)
{
	if (x > end_x || y > end_y)return;
	for (int i = 0; i < 4; i++)
	{
		int now_x = x + dx[i];
		int now_y = y + dy[i];

		if (now_x >= 1 && now_x <= n && now_x >= y && now_y < m && !vis[now_x][now_y])
		{
			vis[now_x][now_y] = 1;//The number of searched is marked as 1 and will be skipped after the next search
			dfs(now_x, now_y, end_x, end_y, geshu + 1);//Add 1 to the number after the next search starts
			vis[now_x][now_y] = 0;

		}

	}
}

Eight queens problem P1219 [USACO1.5] eight queens Checker Challenge - New Ecology of computer science education in Luogu (luogu.com.cn)

The difficulty of this problem is to judge the pieces on the diagonal; How to search diagonals is the key. After determining the diagonal search formula, recursive processing is used.

void dfs(int x)//Where is the queen in line x
{
	if (x > n)
	{
		ans++;
		if (ans <= 3)//The first three cases are output, and all cases can also be output
		{
			for (int i = 1; i <= n; i++)
				cout << a[i] << " ";
			cout << endl;
		}
		return;
	}
 
	for(int i=1;i<=n;i++)
		if (b1[i] == 0 && b2[x + i] == 0 && b3[x - i + 15] == 0)//Can be placed
		{
			a[x] = i;//The queen in row x is placed on column i
			b1[i] = 1;
			b2[x + i] = 1;
			b3[x - i + 15] = 1;
			dfs(x + 1);//Recursive next line
			b1[i] = 0; b2[x + i] = 0; b3[x - i + 15] = 0;//to flash back
		}
}
 

Total permutation problem Total permutation problem - Luogu

First of all, we must understand that each number can only be output once, no more and no less. That is, we need to mark the number used every time. Recursion is used when the output is. For example, the first output is 1, 2 and 3 (this result is easy to realize), but the processing method of the second output is 1, 3 and 2 is the key. For the solution of this problem, I have read many different blogs, among which the exchange of the positions of 2 and 3 is the best way to understand.

void dfs(int x)
{
	if(x==n)
	{
		for(int v=0;v<n;v++)
		{
			cout<<d(v);
		}
		return ;
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			if(c[i]==0)
			{
				d[x]=a[i];//assignment
				c[i]=1;//sign
				dfs(x+1);//recursion
				c[i]=0;//to flash back
			}
		}
	}
	
}

[USACO10OCT]Lake Counting S - Los Angeles Valley The character 'W' is found in the map array and this position has not been passed. Call the number of puddles plus 1. Mark the passing position

#include <iostream>
using namespace std;

const int N = 110;

int n, m;
char g[N][N];
bool st[N][N];

void dfs(int x, int y)
{
	st[x][y] = true;
	for (int i = -1; i <= 1; i ++)
		for (int j = -1; j <= 1; j ++)
		{
			int a = x + i, b = y + j;
			if(a < 1 || a > n || b < 1 || b > m) continue;
			if(g[a][b] == '.' || st[a][b]) continue;
			
			dfs(a, b);
		}
}

int main()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			cin >> g[i][j];
			
	int ans = 0;		
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if(g[i][j] == 'W' && !st[i][j])
			{
				ans ++;
				dfs(i, j);
			}		
			
	cout << ans << endl;
	return 0;		
}

This is the summary of this week. The key to deep search is recursion. Now there are specific methods for different topics. For this kind of problems, I still need to practice more and have my own ideas.

For search type problems, I can only use recursion, that is, deep search processing, and will not use wide search. When reading the blog, I saw many methods of wide search to deal with problems. Next week, I will strengthen my understanding of wide search and use wide search to deal with problems.