preface
Tip: the following is the main content of this article. The following cases can be used for reference
I P1683 getting started
Title Description
Not everyone can enter Taohua island. Pharmacist Huang hates people as stupid as Guo Jing. Therefore, he built a path at the only entrance to Taohua Island, which was all paved with square tiles. Some ceramic tiles can be stepped on, which we think is safe, while some ceramic tiles will emit deadly poison gas as soon as they are stepped on, so you will die. We think it is unsafe. You can only walk from one safe tile to any of the four adjacent tiles, but it must also be safe.
As you are a friend of Huang Rong, she tells you which bricks are safe and which are unsafe in advance, and she will guide you to fly to the first brick (the first brick may be in any safe position). Now she tells you the secret of entering Taohua Island: if you can walk through the most tiles and don't die, the door of Taohua island will open automatically, You can fly directly into the gate from your current position.
Note: tiles can be passed repeatedly, but cannot be counted repeatedly.
Input format
In the first line, two positive integers WW and HH represent the width and length of the path respectively.
The following HH acts as an H\times WH × Character matrix of W. Each character represents a tile. Where,. Represents the safe brick, # represents the unsafe brick, and @ represents the first brick.
Output format
The output line includes only one number, that is, the maximum number of bricks you can safely walk through from the first brick (including the first brick).
Input and output samples
input output 11 9 59 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ...........
1. Deep search template I
#include <bits/stdc++.h>
using namespace std;
char a[25][25];
int vis[25][25];
int w,h,sx,sy,ans;
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void dfs(int x,int y){
for(int i=0;i<4;i++){
int ux=x+d[i][0],uy=y+d[i][1];
if(ux<=h&&uy<=w&&ux>=1&&uy>=1&&a[ux][uy]=='.'&&!vis[ux][uy]){
ans++;
vis[ux][uy]=1;
dfs(ux,uy);
}
}
}
int main()
{
cin>>w>>h;
for(int i=1;i<=h;i++)
for(int j=1;j<=w;j++){
cin>>a[i][j];
if(a[i][j]=='@') sx=i,sy=j;
}
ans++;
vis[sx][sy]=1;
dfs(sx,sy);
cout<<ans;
return 0;
}
2. Deep search template II
#include <bits/stdc++.h>
using namespace std;
char a[25][25];
bool vis[25][25];
int h,w,sx,sy,ans;
int d[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
inline void dfs(int x,int y){
if(x<1||y<1||x>w||y>h||vis[x][y]!=0||a[x][y]=='#') return ;
vis[x][y]=1;
ans++;
dfs(x-1,y);
dfs(x,y-1);
dfs(x+1,y);
dfs(x,y+1);
}
int main()
{
cin>>h>>w;
for(int i=1;i<=w;i++)
for(int j=1;j<=h;j++){
cin>>a[i][j];
if(a[i][j]=='@'){
sx=i;
sy=j;
}
}
dfs(sx,sy);
cout<<ans;
return 0;
}
II P2404 splitting of natural numbers
Title Description
Any natural number n greater than 1 can always be divided into the sum of several natural numbers less than n. Now I'll give you a natural number N and ask you to find the sum of N divided into some numbers. The numbers in each split sequence are sorted from small to large. Then you need to output these sequences, and the sequences with small dictionary order need to be output first.
Input format
Input: natural number to be split n.
Output format
Output: the adder of several numbers.
Input and output samples
input output 7 1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+1+3 1+1+1+2+2 1+1+1+4 1+1+2+3 1+1+5 1+2+2+2 1+2+4 1+3+3 1+6 2+2+3 2+5 3+4 ...........
#include <iostream>
using namespace std;
int n,a[25];
void dfs(int he,int cnt,int sx){
if(he==n){
for(int i=1;i<=cnt-2;i++)
cout<<a[i]<<"+";
cout<<a[cnt-1]<<endl;
return;
}
if(he>n) return;
for(int i=sx;i<=n-1;i++){
a[cnt]=i;
dfs(he+i,cnt+1,i);
a[cnt]=0;
}
}
int main()
{
cin>>n;
dfs(0,1,1);
return 0;
}
III P1332 bloody Vanguard (multi starting point search)
Topic background
The Lich King's Scourge army finally made a comeback. The bloody Crusader organized a vanguard army to Northrend to fight against the Scourge army and all creatures with the smell of the dead. The bloody vanguard army isolated from the alliance and tribe was soon surrounded by the Scourge army. Now they have to gather their main force to resist the encirclement and suppression of the Scourge army. The terrible thing is that some of them are infected with the plague of the dead. If they do not try to stop the spread of the plague, they will soon be destroyed. Highlord abidis has begun to investigate the source of the plague. It turned out that there was a traitor inside the bloody pioneer army. The traitor has taken refuge in the Scourge army and wants to turn the whole bloody pioneer army into the Scourge army! Not surprisingly, you are the traitor. Before your whereabouts are revealed, complete the task assigned to you by the Lich King as soon as possible.
Title Description
The Legion is a matrix with nn rows and mm columns, and each unit is a member of the blood pioneer army. People infected with the plague will spread the plague around every hour until all people are infected with the plague. You have mastered the location of the source of infection. Your task is to calculate the time when the Lords of the blood pioneer army were infected with the plague and report it to the Lich King, so as to carry out a round of targeted encirclement and suppression of the blood pioneer army.
Input format
Row 11: four integers nn, mm, aa, bb, indicating that the Legion matrix has nn rows and mm columns. There are aa infection sources, bb is the number of Lords in the bloody death squads.
Next line aa: each line has two integers xx and yy, indicating that the infection source is in line xx and column yy.
Next bb line: each line has two integers xx and yy, indicating that the position of the Lord is in line xx and column yy.
Output format
Lines 11 to bb: an integer in each line indicates the time when the LORD was infected with the plague. The output order is consistent with the input order. If a person's location is at the source of infection, the time when he is infected with the plague is 00.
input output 5 4 2 3 3 1 1 1 5 4 3 3 3 5 3 2 4 ...........
#include <bits/stdc++.h>
using namespace std;
int n,m,a,b;
struct sq{
int x,y,step;
};
queue<sq> q;
int mp[520][520];
bool vis[520][520];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
void ru(int x,int y){
sq tmp={x,y,0};
q.push(tmp);
vis[x][y]=1;
return;
}
void bfs(){
while(!q.empty()){
sq u;
for(int i=0;i<4;i++){
u=q.front();
int ux=u.x,uy=u.y;
int dx=ux+d[i][0],dy=uy+d[i][1];
if(dx<1||dy<1||dx>n||dy>m||vis[dx][dy]) continue;
vis[dx][dy]=1;
sq tmp={dx,dy,u.step+1};
q.push(tmp);
}
mp[u.x][u.y]=u.step;
q.pop();
}
}
int main()
{
memset(vis,false,sizeof(vis));
cin>>n>>m>>a>>b;
int x,y;
for(int i=1;i<=a;i++){
cin>>x>>y;
ru(x,y);
}
bfs();
for(int i=1;i<=b;i++){
cin>>x>>y;
cout<<mp[x][y]<<endl;
}
return 0;
}
4, Memorized dfs
P1434 [show2002] skiing
Title Description
Michael likes skiing. This is not surprising, because skiing is really exciting. However, in order to get speed, the sliding area must tilt downward, and when you slide to the bottom of the slope, you have to go up the slope again or wait for the elevator to pick you up. Michael wants to know the longest landslide in an area. The region is given by a two-dimensional array. Each number in the array represents the height of the point. Here is an example:
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
A person can slide up and down from a point to one of the four adjacent points on the left and right if and only if the height decreases. In the above example, a feasible landslide is 2424-1717-1616-11 (starting from 2424 and ending at 11). Of course, 2525-2424-2323 - \ ldots... - 33-22-11 is longer. In fact, this is the longest one.
Input format
The first input line represents the row number RR and column number cc of the two-dimensional array of the region. The following is the RR line. Each line has CC numbers, representing the height (11 spaces between the two numbers).
Output format
The length of the longest landslide in the output area.
Input and output samples
input output 1 2 3 4 5 25 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
#include <bits/stdc++.h>
using namespace std;
int n,m,minn=INT_MAX;
int step;
int a[105][105];
int sx[105][105];
int d[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
int dfs(int x,int y){
if(sx[x][y]) return sx[x][y];
sx[x][y]=1;
for(int i=0;i<4;i++){
int dx=x+d[i][0],dy=y+d[i][1];
if(dx>=1&&dy>=1&&dx<=n&&dy<=m&&a[dx][dy]<a[x][y]){
dfs(dx,dy);
sx[x][y]=max(sx[dx][dy]+1,sx[x][y]);
}
}
return sx[x][y];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
step=max(dfs(i,j),step);
cout<<step;
return 0;
}
V Word matrix (determine the direction before searching)
Title Description
Give an n \times nn × The letter matrix of N may contain multiple "yizhong" words. Words are placed continuously in the same direction in the square matrix. The placement can follow any of the 88 directions. When placing the same word, the direction will not be changed. Words can cross, so it is possible to share letters. When outputting, replace letters that are not words with * to highlight words. For example:
Input: output:
8
qyizhong *yizhong gydthkjy gy****** nwidghji n*i***** orbzsfgz o**z**** hhgrhwth h***h*** zzzzzozo z****o** iwdfrgng i*****n* yyyygggg y******g
Input format
Enter a number nn in the first line. (7 \le n \le 1007≤n≤100).
The second line starts with n \times nn × Letter matrix of n.
Output format
Highlight the n \times nn of the word × N matrix.
Input and output samples
#include <bits/stdc++.h>
#define maxn 110
using namespace std;
struct node{
int x,y;
}c[maxn];
char sz[maxn][maxn],stand[]="yizhong";
int vis[maxn][maxn];
int walk[8][2]={{0,1},{0,-1},{1,0},{-1,0},{-1,-1},{-1,1},{1,-1},{1,1}};
int n;
void dfs(int x,int y,node c[],int k,int cur){
if(cur==7){
for(int i=0;i<7;i++)
vis[c[i].x][c[i].y]=1;
}else{
int dx=x+walk[k][0],dy=y+walk[k][1];
if(cur==6||sz[dx][dy]==stand[cur+1]){
c[cur].x=x;
c[cur].y=y;
dfs(dx,dy,c,k,cur+1);
}
}
}
int main()
{
cin>>n;
memset(vis,0,sizeof(vis));
for(int i=0;i<n;i++)
scanf("%s",sz[i]);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(sz[i][j]=='y'){
for(int k=0;k<8;k++){
int x=i+walk[k][0],y=j+walk[k][1];
if(sz[x][y]=='i'){
dfs(i,j,c,k,0);
}
}
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(vis[i][j]==1)
cout<<sz[i][j];
else cout<<"*";
}
cout<<endl;
}
return 0;
}