(Luogu) p1162 p1019

本文主要是介绍(Luogu) p1162 p1019，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

很久没做搜索题了，做了两道

1.p1162填涂颜色 https://www.luogu.org/problemnew/show/P1162

很明显的宽搜题。不过不好从要求的搜索，从边界搜索易解。

#include<bits/stdc++.h>
using namespace std;
int n;
int a[40][40];
int x[]={0,0,1,-1};
int y[]={1,-1,0,0};
void bfs(int i,int j){a[i][j]=-1;queue<pair<int,int> > q;q.push(make_pair(i,j));pair<int,int> temp;while(!q.empty()){temp=q.front();q.pop();int xx=temp.first,yy=temp.second;
//		cout<<xx<<' '<<yy<<endl; for(int t=0;t<4;++t){if(xx+x[t]!=0&&xx+x[t]!=n+1&&yy+y[t]!=0&&yy+y[t]!=n+1&&a[xx+x[t]][yy+y[t]]==0){a[xx+x[t]][yy+y[t]]=-1;q.push(make_pair(xx+x[t],yy+y[t]) );}}}}
int main(){cin>>n;for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){cin>>a[i][j];}}for(int i=1;i<=n;++i){//遍历上下左右边界 if(a[1][i]==0)	bfs(1,i);if(a[n][i]==0)	bfs(n,i);if(a[i][1]==0)	bfs(i,1);if(a[i][n]==0)	bfs(i,n);}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){if(a[i][j]==-1)	cout<<0<<' ';if(a[i][j]==1)	cout<<1<<' ';if(a[i][j]==0)	cout<<2<<' ';}cout<<endl;}return 0;
} 

2.P1019 单词接龙https://www.luogu.org/problemnew/show/P1019

首先要预处理一下，然后是深搜加回溯吧

#include<bits/stdc++.h>
using namespace std;
string s[25];
int countt[25],num[25][25];//countt记录每个使用次数，num第i个后接第j个最小重合个数
int n,INF=-12345;
int ans=-1;
int nn=0;
int fun(int i,int j){//第i个后面接第j个 int res=0;for(int k=s[i].size()-1;k>=0/*&&k>=s[i].size()-s[j].size()*/;k--){int t,st=0;for(t=k;t<s[i].size();++t){if(s[i][t]==s[j][st]&&st!=s[j].size()){st++;}else	break;}if(t>=s[i].size()){return s[i].size()-k;}}return INF;
} 
void dfs(int p){bool pd=0;for(int i=0;i<n;++i){if(countt[i]>=2||num[p][i]==INF||num[p][i]==s[p].size()||num[p][i]==s[i].size())continue;int len=s[i].size()-num[p][i];nn+=len;countt[i]++,pd=1;dfs(i);nn-=len,countt[i]--;}if(!pd){ans=max(ans,nn);}return ;
}int main(){cin>>n;for(int i=0;i<n;++i){cin>>s[i];}char start;cin>>start;for(int i=0;i<n;++i){for(int j=0;j<n;++j){num[i][j]=fun(i,j);}}
//	for(int i=0;i<n;++i){
//		for(int j=0;j<n;++j){
//			cout<<num[i][j]<<' ';
//		}
//		cout<<endl;
//	}for(int i=0;i<n;++i){if(s[i][0]==start){countt[i]++;nn=s[i].size();dfs(i);countt[i]=0;}	}cout<<ans<<endl;return 0;
}

 

这篇关于(Luogu) p1162 p1019的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---