This week ended the search list and began to brush the three list and two-point list of mathematics, which is expected to end 14 weeks ago.
Deep search about maps:
1. Pay attention to the boundary. (note that when using memset, it should be considered clearly. Unnecessary parts may also be initialized, affecting the search). 2. The difference between different topics lies in the different if statements in the search. It is not very complex to write according to the meaning of the topic.
3. Termination condition: return when it is satisfied. It may be to find the number of schemes or to reach the minimum number of steps.
(carry out backtracking and mark the passed points in the initialization state to facilitate the next layer of circulation)
Template questions: P1605 maze
#include <bits/stdc++.h>
using namespace std;
int n,m,t,sx,sy,fx,fy,ans;
int mp[10][10],vis[10][10];
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
void dfs(int x,int y)
{
if(x==fx&&y==fy)
{
ans++;
return;
}
for(int i=0;i<4;i++)
{
if(vis[x+dx[i]][y+dy[i]]==0&&mp[x+dx[i]][y+dy[i]]==1)
{
vis[x][y]=1;
dfs(x+dx[i],y+dy[i]);
vis[x][y]=0;
}
}
}
int main()
{
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
mp[i][j]=1;
for(int i=1;i<=t;i++)
{
int l,r;
cin>>l>>r;
mp[l][r]=0;
}
dfs(sx,sy);
cout<<ans<<endl;
return 0;
}
P1019 [NOIP2000 improvement group] word Solitaire
Title Requirements:
1. Find the string with the largest splicing length.
2. A word can be used up to 2 times.
3. Strings containing relationships cannot be spliced.
Train of thought:
1. Since the beginning of "dragon" is specified, the length is accumulated from 1.
2. Write a function to return the number of overlapping parts of two strings.
3.dfs traversal, considering twice for each string.
Method to get two string ending repeating elements:
int rp(string s1,string s2)
{
for(int i=1;i<min(s1.length(),s2.length());i++)
{
bool f=1;
for(int j=0;j<i;j++)
{
if(s1[s1.length()-i+j]!=s2[j]) f=0;
}
if(f) return i;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n,lg,num[30];
string st[30];
int rp(string s1,string s2)
{
for(int i=1;i<min(s1.length(),s2.length());i++)
{
bool f=1;
for(int j=0;j<i;j++)
{
if(s1[s1.length()-i+j]!=s2[j]) f=0;
}
if(f) return i;
}
return 0;
}
void dfs(string s,int lg1)
{
lg=max(lg,lg1);
for(int i=0;i<n;i++)
{
if(num[i]>=2) continue;
int tmp=rp(s,st[i]);
if(tmp>0)
{
num[i]++;
dfs(st[i],lg1+st[i].length()-tmp);
num[i]--;
}
}
}
int main()
{
cin>>n;
for(int i=0;i<=n;i++)
cin>>st[i];
dfs(' '+st[n],1);
cout<<lg<<endl;
return 0;
}
It may be a boundary problem. The last set of data always returns re. But with the boundary, everything else can pass. The last set of data is wr. It should be some details of the code, but it just can't be found.....
#include <bits/stdc++.h>
using namespace std;
int n,d,s[105][105],c[105][2];
bool vis[105][105];
char ch[105][105];
string s1=" yizhong";
int dx[9]={0,0,0,-1,-1,-1,1,1,1};
int dy[9]={0,1,-1,0,-1,1,0,-1,1};
int dfs(int i,int j,int x,int y,int m)
{
if(m>7)
{
vis[i][j]=1;
return 1;
}
if(ch[i+x][j+y]==s1[m])
{
if(dfs(i+x,j+y,x,y,m+1))
{
vis[i][j]=1;
return 1;
}
}
}
int main()
{
freopen("in.txt","r",stdin);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>ch[i][j];
if(ch[i][j]=='y')
{
c[++d][0]=i;c[d][1]=j;
}
}
while(d)
{
int i=c[d][0];
int j=c[d][1];
for(int k=1;k<=8;k++)
{
if(ch[i+dx[k]][j+dy[k]]=='i')
if(dfs(i+dx[k],j+dy[k],dx[k],dy[k],3))
vis[i][j]=1;
}
d--;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(vis[i][j])
cout<<ch[i][j];
else
cout<<"*";
}
cout<<endl;
}
return 0;
}
P2404 splitting of natural numbers
Split the number n layer by layer and traverse a variety of possibilities by backtracking. (it's better to simulate the process to understand the recursive process)
#include <iostream>
using namespace std;
int n,a[3005]={1};
void dfs(int s,int g)
{
int i;
for(i=a[g-1];i<=s;i++)
{
if(i<n)
{
a[g]=i;
s-=i;
if(s==0)
{
for(int j=1;j<=g-1;j++)
cout<<a[j]<<"+";
cout<<a[g]<<endl;
}
else
{
dfs(s,g+1);
}
s+=i;
}
}
}
int main()
{
cin>>n;
dfs(n,1);
return 0;
}
P1596 [USACO10OCT]Lake Counting S
A problem of DFS judging connected blocks. The trick of this problem is that generally, we will open an array of points traversed as "W" for marking, and this problem will directly change "W" into ".", which is very clever.
#include <bits/stdc++.h>
using namespace std;
int n,m,ans;
char ch[105][105];
int dx[9]={0,0,0,1,1,1,-1,-1,-1};
int dy[9]={0,1,-1,0,1,-1,0,-1,1};
void dfs(int x,int y)
{
ch[x][y]='.';
for(int i=1;i<=8;i++)
{
if(x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m&&ch[x+dx[i]][y+dy[i]]=='W')
dfs(x+dx[i],y+dy[i]);
}
}
int main()
{
//freopen("in.txt","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cin>>ch[i][j];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(ch[i][j]=='W'){
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
Coloring problem: pay attention to the boundary. You should search the outer circle first, and then an error will appear (the edge is colored). In this case, because the boundary is limited by the scope, it will be mistaken for being 1 wrapped.
void dfs(int x,int y) //There are two ways to write recursion. Considering the peripheral circle, this recursive way should search from itself
{
for(int i=0;i<=4;i++)
{
if(x+dx[i]>=0&&x+dx[i]<=n+1&&y+dy[i]>=0&&y+dy[i]<=n+1&&vis[x+dx[i]][y+dy[i]]==0)
{
vis[x][y]=1;
dfs(x+dx[i],y+dy[i]);
}
}
}
#include <bits/stdc++.h>
using namespace std;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int a[50][50];
int n;
void dfs(int x,int y)
{
if(x>=0 && x<=n+1 && y>=0&& y<=n+1)
{
if(a[x][y]==1||a[x][y]==3)
return ;
else
{
a[x][y]=3;
for(int i=1;i<=4;i++)
dfs(x+dx[i],y+dy[i]);
}
}
}
int main()
{
freopen("in.txt","r",stdin);
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>a[i][j];
}
}
dfs(0,0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==3)
cout<<0<<" ";
else if(a[i][j]==0)
cout<<2<<" ";
else
cout<<1<<" ";
}
cout<<endl;
}
return 0;
}
Two points (review of lower_bound() and upper_bound())
P2249 [deep foundation 13. Example 1] search
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
while(m--)
{
int tmp;
cin>>tmp;
int k=lower_bound(a,a+n,tmp)-a;
if(tmp==a[k])
cout<<k+1<<" ";
else
cout<<-1<<" ";
}
cout<<endl;
return 0;
}
[algorithm 1-6] binary search and binary answer
#include <bits/stdc++.h>
using namespace std;
long long a[200005];
int main()
{
long long n,c;
cin>>n>>c;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
long long ans=0;
for(int i=0;i<n;i++){
long long a1=upper_bound(a,a+n,a[i]+c)-a;
long long a2=lower_bound(a,a+n,a[i]+c)-a;
ans+=a1-a2;
}
cout<<ans<<endl;
return 0;
}