|
??????? 这两天学的是广搜（bfs），做的题挺少的，到现在还没做完习题，只能说是现在遇到广搜的题有了点大概的思路，下面记录一下自己做的题（重复题型的就不记录了）。
hdu4460
https://acm.hdu.edu.cn/showproblem.php?pid=4460
题意看了好一阵子还是看不明白，可能是英语水平变垃圾了，最后看的题解才知道题目让求一个k，使得每个人都可以与别人构成朋友链，链子的长度不大于k。还是用bfs（毕竟做的是bfs专题嘛），对每个人都要搜一遍，重点是统计每个人的交友关系，验证每个人是否与别人是不是朋友，求出，满足条件的k。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#define ll long long
#define CHECK(x,y,z) (x>=0&&x<a&&y>=0&&y<b&&z>=0&&z<c&&!(vis[x][y][z])&&val[x][y][z])
//#include<bits/stdc++.h>
using namespace std;
vector<int>v[1015];
map<string,int>mp;
int f,ans,vis[1010];
int n,m;
void bfs(int x){
if(!f) return;
queue<int>q;
memset(vis,-1,sizeof(vis));
q.push(x);
vis[x]=0;
while(!q.empty()){
int y=q.front();
q.pop();
if(vis[y]>ans){//求ans
ans=vis[y];
if(ans>6){
f=0;
return;
}
}
for(int i=0;i<v[y].size();i++){
if(vis[v[y][i]]==-1){
vis[v[y][i]]=vis[y]+1;//记录每个人的交友情况
q.push(v[y][i]);
}
}
}
for(int i=0;i<n;i++){
if(vis[i]==-1){
f=0;return;
}
}
}
int main(){
// freopen("in.txt","r",stdin);
string s,s1,s2;
while(cin>>n&&n){
for(int i=0;i<n;i++){
cin>>s;
mp[s]=i;
}
cin>>m;
for(int i=0;i<m;i++){
cin>>s1>>s2;
v[mp[s1]].push_back(mp[s2]);//用map将字符串转化为数字便于统计
v[mp[s2]].push_back(mp[s1]);
}
ans=0,f=1;
for(int i=0;i<n;i++){
bfs(i);
}
if(!f) cout<<-1<<endl;
else cout<<ans<<endl;
for(int i=0;i<n;i++) v[i].clear();
}
return 0;
}
poj3278
http://poj.org/problem?id=3278
? 思路还是很清晰的，但是我发现我竟然不会打。。。明明这个题很简单 Orz，famer只有三种选择位置+1，-1或*2，所以根据这三种情况来广搜就行，但是在记录步数和标记已走过的位置时我有点不会打了，最后还是看的题解才恍然大悟，可恶啊，继续加油，淦！
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#define ll long long
#define CHECK(x,y,z) (x>=0&&x<a&&y>=0&&y<b&&z>=0&&z<c&&!(vis[x][y][z])&&val[x][y][z])
//#include<bits/stdc++.h>
using namespace std;
int n,k,a[100010];
void bfs(int n,int k){
memset(a,0,sizeof(a));
queue<int>q;
q.push(n);
a[n]=0;
bool vis[100010];
memset(vis,0,sizeof(vis));
vis[n]=1;
int fir,sec;
while(!q.empty()){
fir=q.front();
// cout<<fir<<endl;
q.pop();
for(int i=0;i<3;i++){
if(i==0) sec=fir+1;
if(i==1) sec=fir-1;
if(i==2) sec=fir*2;
if(sec>=0&&sec<=100000&&(!vis[sec])){
a[sec]=a[fir]+1;
q.push(sec);
vis[sec]=1;
}
if(sec==k){
cout<<a[sec]<<endl;
return;
}
}
}}
int main(){
// freopen("in.txt","r",stdin);
cin>>n>>k;
if(n>=k){
cout<<n-k<<endl;
}
else bfs(n,k);
return 0;
}
poj1426
http://poj.org/problem?id=1426
m是1和0组成的十进制的数，那么bfs就是两个方向，从1开始，逐次*10或*10+1，直到搜出最后结果，感觉这是一道很简单的题，但是c++编译器就是不给我过！，用G++一下子就过了，这是第一道自己做出来的搜索题，泪目了，看来是时候吃根冰棍庆祝一下了！另外看的别人的代码发现深搜c++也可以过，等学了深搜后再来看一遍。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<vector>
#include<queue>
#include<list>
#include<stack>
#include<set>
#define ll long long
#define CHECK(x,y,z) (x>=0&&x<a&&y>=0&&y<b&&z>=0&&z<c&&!(vis[x][y][z])&&val[x][y][z])
//#include<bits/stdc++.h>
using namespace std;
ll n;
void bfs(ll n){
queue<ll>q;
ll m;
q.push(1);
while(!q.empty()){
m=q.front();
q.pop();
if(m%n==0){
cout<<m<<endl;
return;
}
q.push(m*10);
q.push(m*10+1);
}
}
int main(){
// freopen("in.txt","r",stdin);
while(cin>>n&&n>0&&n<=200){
bfs(n);
}
return 0;
}
|