本专题主要锻炼搜索的两大方法——bfs （宽度优先搜索）和 dfs （深度优先搜索）
===================================华丽的分割线=======================================
一、bfs——宽度优先搜索（Breadth First Search）
bfs主要运用于搜索中求最短时间的问题，搜索过程中一般需要运用 queue 的操作。
bfs的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。
具体的操作如下：
1.首先需要将 队列 和 visit数组 清空。（这一点很重要！！！）
2.然后将起点信息 push 进队列，标记为visited（修改 visit 数组中元素对应的值），信息一般都用结构体存储，当然，所建立的 queue 也必须是结构体类型的。
3.接下来就是主体了——一个while循环，判断条件为 队列非空。
每次循环，需要取出队首元素，然后 pop 出队首元素。首先判断是否已满足题目要求，满足的话 return 所需要的信息，否则以该元素为中心，遍历四周的节点，如果节点可以到达且未被访问，则将该节点的信息 push 进队列，并标记为visited。重复循环即可。
4.如果到达while循环外面，说明题目的要求无法达到，返回 impossible 即可。
伪代码如下：（凯神提供！！！快去仰慕）
Q empty
init state - s
Q push s
visite s
while(Q ! empty)
{
state now = Q front
Q pop
next = update now
if(next not visited)
{
Q push next
visite next
}
}
return impossible
几个注意点：
1.各个数据的清空和初始化
2.遍历四周的节点可以用一个for循环，具体实现方法请看最后的题解。
===============================华丽的分割线的大儿子=================================
二、dfs——深度优先检索（Depth First Search）
dfs主要运用于求解满足题目的所有可能的解法的数目，显然这种问题无法用 bfs 解决，因为 bfs 只能求解最优解，而用 dfs 就可以了。
dfs所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点v的所有边都已被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程反复进行直到所有结点都被发现为止。
深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索递归调用包含以下操作：
（1）访问搜索到的未被访问的邻接点；
（2）将此顶点的visited数组元素值置1；
（3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。
dfs可描述为：
（1）访问v0顶点；
（2）置 visited[v0]=1；
（3）搜索v0未被访问的邻接点w，若存在邻接点w，则dfs(w)。
遍历过程：
dfs 在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点w1；再从 w1 出发，访问与 w1邻 接但还没有访问过的顶点 w2；然后再从 w2 出发，进行类似的访问，… 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
深度优先搜索基本算法如下{递归算法}：
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子结点 mr 符合条件 THEN
BEGIN
产生的子结点mr入栈；
IF 子结点mr是目标结点
THEN 输出
ELSE dfs_try(i+1);
栈顶元素出栈;
END;
END;
==============================华丽的分割线的小儿子==================================
题目链接：https://vjudge.net/contest/65959
简单搜索专题题解
A. POJ 1321 棋盘问题
题目要求求出可行解的数目，显然要用dfs，代码如下：
1 #include<iostream> 2 #include<cstring> 3 4 using namespace std; 5 6 char a[8][8]; 7 int num,n,k; 8 9 struct node 10 { 11 int c[8]; 12 int count; 13 }; 14 15 void dfs(int x,struct node map) 16 { 17 if(x>=n) 18 return; 19 /*if(map.count==k) 20 { 21 num++; 22 return; 23 }*/ 24 for(int i=0;i<n;i++) 25 { 26 if(a[x][i]=='.') 27 continue; 28 29 if(map.c[i]==0) 30 { 31 struct node map1; 32 // memcpy(map1.b,map.b,sizeof(map.b)); 33 memcpy(map1.c,map.c,sizeof(map.c)); 34 map1.count=map.count; 35 36 map1.count++; 37 map1.c[i]=1; 38 if(map1.count==k) 39 { 40 num++; 41 // dfs(x+1,map); 42 // cout<<num<<endl; 43 continue; 44 } 45 else 46 { 47 dfs(x+1,map1); 48 } 49 } 50 } 51 dfs(x+1,map); 52 } 53 54 int main() 55 { 56 while(cin>>n>>k) 57 { 58 if(n==-1&&k==-1) 59 break; 60 for(int i=0;i<n;i++) 61 { 62 for(int j=0;j<n;j++) 63 cin>>a[i][j]; 64 } 65 num=0; 66 struct node map; 67 // memset(map.b,0,sizeof(map.b)); 68 memset(map.c,0,sizeof(map.c)); 69 map.count=0; 70 //cout<<num<<endl; 71 dfs(0,map); 72 cout<<num<<endl; 73 } 74 return 0; 75 }
B. POJ 2251 Dungeon Master
很明显是bfs，代码如下：
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 5 using namespace std; 6 7 struct node 8 { 9 int a,b,c; 10 int time; 11 }; 12 13 queue<struct node> t; 14 int l,r,c; 15 int v[35][35][35]; 16 struct node s,e; 17 int m[6][3]={{1,0,0},{-1,0,0},{0,1,0},{0,-1,0},{0,0,1},{0,0,-1}}; 18 19 int bfs() 20 { 21 while(!t.empty()) 22 t.pop(); 23 t.push(s); 24 while(!t.empty()) 25 { 26 struct node d; 27 d=t.front(); 28 if(d.a==e.a&&d.b==e.b&&d.c==e.c) 29 return d.time; 30 t.pop(); 31 int x=d.a,y=d.b,z=d.c; 32 d.time++; 33 34 for(int i=0;i<6;i++) 35 { 36 d.a=x+m[i][0]; 37 d.b=y+m[i][1]; 38 d.c=z+m[i][2]; 39 if(d.a>=0&&d.a<l&&d.b>=0&&d.b<r&&d.c>=0&&d.c<c&&!v[d.a][d.b][d.c]) 40 { 41 t.push(d); 42 v[d.a][d.b][d.c]=1; 43 } 44 } 45 } 46 return 0; 47 } 48 49 int main() 50 { 51 while(cin>>l>>r>>c) 52 { 53 if(l==0&&r==0&&c==0) 54 break; 55 //memset(v.0.sizeof(v)); 56 for(int i=0;i<l;i++) 57 { 58 for(int j=0;j<r;j++) 59 { 60 for(int k=0;k<c;k++) 61 { 62 char c; 63 cin>>c; 64 if(c=='#') 65 v[i][j][k]=1; 66 if(c=='.') 67 v[i][j][k]=0; 68 if(c=='S') 69 { 70 s.a=i; 71 s.b=j; 72 s.c=k; 73 s.time=0; 74 v[i][j][k]=1; 75 } 76 if(c=='E') 77 { 78 e.a=i; 79 e.b=j; 80 e.c=k; 81 v[i][j][k]=0; 82 } 83 } 84 // char s; 85 // cin>>s; 86 } 87 // cin.ignore(); 88 } 89 int flag=bfs(); 90 if(!flag) 91 cout<<"Trapped!"<<endl; 92 else 93 cout<<"Escaped in "<<flag<<" minute(s)."<<endl; 94 } 95 return 0; 96 }
C. POJ 3278 Catch That Cow
bfs，代码如下：
1 #include<iostream> 2 #include<queue> 3 #include<cstring> 4 5 using namespace std; 6 7 struct node 8 { 9 int point; 10 int time; 11 }; 12 13 queue<node> t; 14 int n,k; 15 int v[100010]; 16 17 int bfs() 18 { 19 while(!t.empty()) 20 { 21 struct node b; 22 b=t.front(); 23 v[b.point]=1; 24 if(b.point==k) 25 return b.time; 26 t.pop(); 27 int c=b.point; 28 b.time++; 29 b.point=c+1; 30 if(b.point>=0&&b.point<=100000&&b.point<=k&&!v[b.point]) 31 { 32 t.push(b); 33 v[b.point]=1; 34 } 35 b.point=c-1; 36 if(b.point>=0&&b.point<=100000&&!v[b.point]) 37 { 38 t.push(b); 39 v[b.point]=1; 40 } 41 b.point=c*2; 42 if(c<k&&b.point<=100000&&!v[b.point]) 43 { 44 t.push(b); 45 v[b.point]=1; 46 } 47 } 48 } 49 50 int main() 51 { 52 while(cin>>n>>k) 53 { 54 struct node a; 55 a.point=n; 56 a.time=0; 57 while(!t.empty()) 58 t.pop(); 59 t.push(a); 60 memset(v,0,sizeof(v)); 61 v[a.point]=1; 62 cout<<bfs()<<endl; 63 } 64 return 0; 65 }
D. POJ 3279 Fliptile
这道题是dfs的思路。因为只要将第一行的状态确定了，为了达到题目要求，接下来几行的翻转情况也随之确定，所以只需枚举第一行的翻转情况，再更新翻转数组，最后判断最后一行是否满足条件即可。代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 6 using namespace std; 7 8 int n,m; 9 int t[20][20]; 10 int r[20][20],f[20][20],ans[20][20]; 11 int mo[5][2]={{0,-1},{-1,0},{0,1},{1,0},{0,0}}; 12 13 void tranform(int x,int y) 14 { 15 for(int i=0;i<5;i++) 16 { 17 int a=x+mo[i][0],b=y+mo[i][1]; 18 if(a>=0&&a<m&&b>=0&&b<n) 19 r[a][b]=!r[a][b]; 20 } 21 } 22 23 bool dfs() 24 { 25 for(int i=1;i<m;i++) 26 { 27 for(int j=0;j<n;j++) 28 { 29 if(r[i-1][j]) 30 { 31 f[i][j]=1; 32 tranform(i,j); 33 } 34 } 35 } 36 for(int i=0;i<n;i++) 37 { 38 if(r[m-1][i]) 39 return false; 40 } 41 return true; 42 } 43 44 int main() 45 { 46 while(cin>>m>>n) 47 48 { 49 for(int i=0;i<m;i++) 50 { 51 for(int j=0;j<n;j++) 52 cin>>t[i][j]; 53 } 54 int sum=100000; 55 for(int i=0;i<(1<<n);i++) 56 { 57 memset(f,0,sizeof(f)); 58 memcpy(r,t,sizeof(t)); 59 for(int j=0;j<n;j++) 60 { 61 f[0][j]=i>>j&1;//f[0][j]=i&(1<<j); 62 if(f[0][j]) 63 tranform(0,j); 64 } 65 bool result=dfs(); 66 int s=0; 67 if(result) 68 { 69 for(int j=0;j<m;j++) 70 { 71 for(int k=0;k<n;k++) 72 s+=f[j][k]; 73 } 74 if(sum>s) 75 { 76 for(int j=0;j<m;j++) 77 { 78 for(int k=0;k<n;k++) 79 ans[j][k]=f[j][k]; 80 } 81 sum=s; 82 } 83 } 84 } 85 if(sum==100000) 86 { 87 cout<<"IMPOSSIBLE"<<endl; 88 continue; 89 } 90 91 for(int i=0;i<m;i++) 92 { 93 for(int j=0;j<n;j++) 94 { 95 cout<<ans[i][j]; 96 if(j!=n-1) 97 cout<<" "; 98 } 99 cout<<endl; 100 } 101 } 102 return 0; 103 }
E. POJ 1426 Find The Multiple
bfs，改变一下思路即可，代码如下：
1 #include<iostream> 2 #include<string> 3 #include<queue> 4 5 using namespace std; 6 7 int n; 8 queue<long long int> m; 9 10 11 void bfs() 12 { 13 while(!m.empty()) 14 m.pop(); 15 m.push(1); 16 while(true) 17 { 18 long long int a; 19 a=m.front(); 20 m.pop(); 21 if(a>=n&&a%n==0) 22 { 23 cout<<a<<endl; 24 break; 25 } 26 a=a*10; 27 m.push(a); 28 if(a>=n&&a%n==0) 29 { 30 cout<<a<<endl; 31 break; 32 } 33 a++; 34 m.push(a); 35 } 36 } 37 38 int main() 39 { 40 while(cin>>n&&n) 41 bfs(); 42 return 0; 43 }
F. POJ 3126 Prime Path
bfs，代码如下：
1 #include<iostream> 2 #include<algorithm> 3 #include<cmath> 4 #include<queue> 5 #include<cstring> 6 7 using namespace std; 8 9 struct node 10 { 11 int num; 12 int cost; 13 }; 14 15 int m,n; 16 queue<struct node> p; 17 18 int prime[10000]; 19 int visit[10000]; 20 21 int bfs() 22 { 23 while(!p.empty()) 24 p.pop(); 25 memset(visit,0,sizeof(visit)); 26 struct node t; 27 t.num=m; 28 t.cost=0; 29 p.push(t); 30 visit[m]=1; 31 32 while(!p.empty()) 33 { 34 struct node a; 35 a=p.front(); 36 p.pop(); 37 if(a.num==n) 38 return a.cost; 39 int d[4]; 40 d[0]=a.num%10; 41 d[1]=a.num/10%10; 42 d[2]=a.num/100%10; 43 d[3]=a.num/1000; 44 45 for(int i=0;i<4;i++) 46 { 47 for(int j=0;j<10;j++) 48 { 49 int number=d[i]; 50 if(d[i]!=j) 51 { 52 d[i]=j; 53 struct node b; 54 b.num=d[0]+d[1]*10+d[2]*100+d[3]*1000; 55 b.cost=a.cost+1; 56 if(b.num>1000&&prime[b.num]&&!visit[b.num]) 57 { 58 p.push(b); 59 visit[b.num]=1; 60 } 61 } 62 d[i]=number; 63 } 64 } 65 } 66 return 0; 67 } 68 69 bool isprime(int x) 70 { 71 if(x<=1) 72 return 0; 73 double y=sqrt((double)x); 74 for(int i=2;i<=y;i++) 75 { 76 if(x%i==0) 77 return 0; 78 } 79 return 1; 80 } 81 82 int main() 83 { 84 int t; 85 86 for(int i=1000;i<10000;i++) 87 prime[i]=isprime(i); 88 89 cin>>t; 90 while(t--) 91 { 92 cin>>m>>n; 93 if(m==n) 94 { 95 cout<<"0"<<endl; 96 continue; 97 } 98 int c=bfs(); 99 if(c) 100 cout<<c<<endl; 101 else 102 cout<<"Impossible"<<endl; 103 } 104 return 0; 105 }
G. POJ 3087 Shuffle'm Up
这道题不太像搜索，按照题目要求模拟即可，每次记录下状态，直到满足题目要求或者出现与之前相同的状态。代码如下：
1 #include<iostream> 2 #include<cmath> 3 #include<cstdio> 4 #include<cstring> 5 #include<map> 6 #include<queue> 7 #include<string> 8 9 using namespace std; 10 11 int n,c; 12 string s1,s2,s,ans; 13 map<string,bool> m; 14 15 int main() 16 { 17 18 while(cin>>n) 19 { 20 for(int l=1;l<=n;l++) 21 { 22 m.clear(); 23 cin>>c; 24 cin>>s1>>s2; 25 cin>>ans; 26 int count=0; 27 cout<<l<<" "; 28 s.clear(); 29 while(1) 30 { 31 for(int i=0;i<c;i++) 32 { 33 s.push_back(s2[i]); 34 s.push_back(s1[i]); 35 } 36 count++; 37 // cout<<s<<endl; 38 // cout<<count<<endl; 39 // cout<<m[s]<<endl; 40 if(s==ans) 41 { 42 cout<<count<<endl; 43 break; 44 } 45 if(m[s]) 46 { 47 cout<<-1<<endl; 48 break; 49 } 50 m[s]=true; 51 s1.clear(); 52 s2.clear(); 53 for(int i=0;i<c;i++) 54 { 55 s1.push_back(s[i]); 56 s2.push_back(s[i+c]); 57 } 58 s.clear(); 59 } 60 } 61 } 62 return 0; 63 }
H. POJ 3414 Pots
bfs，代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<string> 9 10 using namespace std; 11 12 struct node 13 { 14 int x,y; 15 int k; 16 vector<string> s; 17 }; 18 19 int a,b,c; 20 int visit[105][105]; 21 queue<struct node> t; 22 struct node ans; 23 24 int min(int x,int y) 25 { 26 return x>y?y:x; 27 } 28 29 bool bfs() 30 { 31 while(!t.empty()) 32 t.pop(); 33 vector<string> m; 34 m.clear(); 35 struct node temp; 36 temp.x=0; 37 temp.y=0; 38 temp.k=0; 39 temp.s=m; 40 t.push(temp); 41 memset(visit,0,sizeof(visit)); 42 visit[0][0]=1; 43 44 while(!t.empty()) 45 { 46 struct node f; 47 f=t.front(); 48 t.pop(); 49 if(f.x==c||f.y==c) 50 { 51 ans=f; 52 return true; 53 } 54 55 struct node f0=f; 56 f0.s.push_back("FILL(1)"); 57 f0.x=a; 58 f0.k++; 59 if(!visit[f0.x][f0.y]) 60 { 61 t.push(f0); 62 visit[f0.x][f0.y]=1; 63 } 64 65 f0=f; 66 f0.s.push_back("FILL(2)"); 67 f0.y=b; 68 f0.k++; 69 if(!visit[f0.x][f0.y]) 70 { 71 t.push(f0); 72 visit[f0.x][f0.y]=1; 73 } 74 75 f0=f; 76 f0.s.push_back("DROP(1)"); 77 f0.x=0; 78 f0.k++; 79 if(!visit[f0.x][f0.y]) 80 { 81 t.push(f0); 82 visit[f0.x][f0.y]=1; 83 } 84 85 f0=f; 86 f0.s.push_back("DROP(2)"); 87 f0.y=0; 88 f0.k++; 89 if(!visit[f0.x][f0.y]) 90 { 91 t.push(f0); 92 visit[f0.x][f0.y]=1; 93 } 94 95 f0=f; 96 f0.s.push_back("POUR(1,2)"); 97 int cha=min(f0.x,b-f0.y); 98 f0.x=f0.x-cha; 99 f0.y=f0.y+cha; 100 f0.k++; 101 if(!visit[f0.x][f0.y]) 102 { 103 t.push(f0); 104 visit[f0.x][f0.y]=1; 105 } 106 107 f0=f; 108 f0.s.push_back("POUR(2,1)"); 109 cha=min(a-f0.x,f0.y); 110 f0.x=f0.x+cha; 111 f0.y=f0.y-cha; 112 f0.k++; 113 if(!visit[f0.x][f0.y]) 114 { 115 t.push(f0); 116 visit[f0.x][f0.y]=1; 117 } 118 } 119 return false; 120 } 121 122 int main() 123 { 124 while(cin>>a>>b>>c) 125 { 126 if(bfs()) 127 { 128 cout<<ans.k<<endl; 129 for(int i=0;i<ans.s.size();i++) 130 cout<<ans.s[i]<<endl; 131 } 132 else 133 cout<<"impossible"<<endl; 134 } 135 return 0; 136 }
I. FZU 2150 Fire Game
bfs，代码如下：
1 #include<iostream> 2 #include<cmath> 3 #include<cstring> 4 #include<queue> 5 6 using namespace std; 7 8 struct node 9 { 10 int x,y; 11 int time; 12 }; 13 14 int n,m,ans,ans0,tem; 15 int visit[15][15]; 16 char map[15][15],map0[15][15]; 17 int mo[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 18 queue<struct node> ma; 19 20 void transform(struct node temp) 21 { 22 for(int i=0;i<4;i++) 23 { 24 int a=temp.x+mo[i][0],b=temp.y+mo[i][1]; 25 if(a>=0&&a<n&&b>=0&&b<m&&map0[a][b]=='#'&&!visit[a][b]) 26 { 27 map0[a][b]='.'; 28 visit[a][b]=temp.time+1; 29 if(visit[a][b]>tem) 30 tem=visit[a][b]; 31 struct node f; 32 f.x=a; 33 f.y=b; 34 f.time=temp.time+1; 35 //tem=f.time; 36 ma.push(f); 37 } 38 } 39 } 40 41 int bfs(int start,int end) 42 { 43 struct node t; 44 t.x=start; 45 t.y=end; 46 t.time=0; 47 ans0=n*m+1; 48 49 for(int i=0;i<n;i++) 50 { 51 for(int j=0;j<m;j++) 52 { 53 if(map[i][j]=='#') 54 { 55 tem=0; 56 while(!ma.empty()) 57 ma.pop(); 58 ma.push(t); 59 60 memset(visit,0,sizeof(visit)); 61 memcpy(map0,map,sizeof(map)); 62 63 visit[start][end]=1; 64 visit[i][j]=1; 65 map0[start][end]='.'; 66 map0[i][j]='.'; 67 68 struct node temp; 69 temp.x=i; 70 temp.y=j; 71 temp.time=0; 72 ma.push(temp); 73 74 while(!ma.empty()) 75 { 76 struct node a=ma.front(); 77 ma.pop(); 78 transform(a); 79 } 80 bool is=true; 81 for(int i=0;i<n;i++) 82 { 83 for(int j=0;j<m;j++) 84 { 85 if(map0[i][j]=='#') 86 { 87 is=false; 88 break; 89 } 90 } 91 } 92 93 if(is==true) 94 { 95 // cout<<tem<<"aaaa"<<endl; 96 if(tem<ans0) 97 ans0=tem; 98 } 99 } 100 } 101 } 102 if(ans0!=n*m+1) 103 return ans0; 104 return -1; 105 } 106 107 int main() 108 { 109 int t; 110 111 while(cin>>t) 112 { 113 for(int l=1;l<=t;l++) 114 { 115 cin>>n>>m; 116 for(int i=0;i<n;i++) 117 { 118 for(int j=0;j<m;j++) 119 cin>>map[i][j]; 120 } 121 ans=n*m+1; 122 for(int i=0;i<n;i++) 123 { 124 for(int j=0;j<m;j++) 125 { 126 if(map[i][j]=='#') 127 { 128 int t=bfs(i,j); 129 // cout<<t<<endl; 130 if(t!=-1) 131 { 132 if(t<ans) 133 ans=t; 134 } 135 } 136 } 137 } 138 cout<<"Case "<<l<<": "; 139 if(ans!=n*m+1) 140 cout<<ans<<endl; 141 else 142 cout<<-1<<endl; 143 } 144 } 145 return 0; 146 }
J. UVA 11624 Fire!
bfs，注意起火点可能不止一个，代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 #include<vector> 7 8 using namespace std; 9 10 struct node 11 { 12 char c; 13 int x,y; 14 int time; 15 }; 16 17 char maze[1000][1000]; 18 int visit[1000][1000]; 19 int r,c,mo[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 20 int jx,jy; 21 vector<int> fx,fy; 22 queue<struct node> map; 23 24 int bfs() 25 { 26 while(!map.empty()) 27 map.pop(); 28 memset(visit,0,sizeof(visit)); 29 30 struct node a; 31 a.c='f'; 32 a.time=0; 33 for(int i=0;i<fx.size();i++) 34 { 35 a.x=fx[i]; 36 a.y=fy[i]; 37 map.push(a); 38 visit[a.x][a.y]=1; 39 } 40 a.c='j'; 41 a.x=jx; 42 a.y=jy; 43 map.push(a); 44 visit[a.x][a.y]=1; 45 46 while(!map.empty()) 47 { 48 struct node temp=map.front(); 49 map.pop(); 50 51 if(temp.c=='f') 52 { 53 for(int i=0;i<4;i++) 54 { 55 int a=temp.x+mo[i][0]; 56 int b=temp.y+mo[i][1]; 57 if(a>=0&&a<r&&b>=0&&b<c&&maze[a][b]!='#'&&!visit[a][b]) 58 { 59 struct node f; 60 f.c='f'; 61 f.x=a; 62 f.y=b; 63 f.time=temp.time+1; 64 map.push(f); 65 visit[a][b]=1; 66 } 67 } 68 } 69 70 if(temp.c=='j') 71 { 72 if(temp.x==0||temp.x==r-1||temp.y==0||temp.y==c-1) 73 return temp.time+1; 74 for(int i=0;i<4;i++) 75 { 76 int a=temp.x+mo[i][0]; 77 int b=temp.y+mo[i][1]; 78 if(a>=0&&a<r&&b>=0&&b<c&&maze[a][b]!='#'&&!visit[a][b]) 79 { 80 struct node f; 81 f.c='j'; 82 f.x=a; 83 f.y=b; 84 f.time=temp.time+1; 85 map.push(f); 86 visit[a][b]=1; 87 } 88 } 89 } 90 } 91 return -1; 92 } 93 94 int main() 95 { 96 int t; 97 98 while(cin>>t) 99 { 100 while(t--) 101 { 102 scanf("%d%d",&r,&c); 103 fx.clear(); 104 fy.clear(); 105 for(int i=0;i<r;i++) 106 { 107 getchar(); 108 for(int j=0;j<c;j++) 109 { 110 scanf("%c",&maze[i][j]); 111 if(maze[i][j]=='J') 112 { 113 jx=i; 114 jy=j; 115 } 116 if(maze[i][j]=='F') 117 { 118 fx.push_back(i); 119 fy.push_back(j); 120 } 121 } 122 } 123 int a=bfs(); 124 if(a==-1) 125 cout<<"IMPOSSIBLE"<<endl; 126 else 127 cout<<a<<endl; 128 } 129 } 130 return 0; 131 }
K. POJ 3984 迷宫问题
bfs 水题， 代码如下：
1 #include<iostream> 2 3 using namespace std; 4 5 int map[5][5]; 6 int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1}; 7 8 struct node 9 { 10 int x, y, pre; 11 }q[100]; 12 13 void print(int i) 14 { 15 if(q[i].pre!=-1) 16 { 17 print(q[i].pre); 18 } 19 cout<<"("<<q[i].x<<", "<<q[i].y<<")"<<endl; 20 } 21 22 void bfs() 23 { 24 int front=0,pen=1; 25 q[front].x=0; 26 q[front].y=0; 27 q[front].pre=-1; 28 29 while(front<pen) 30 { 31 for(int i=0;i<4;i++) 32 { 33 int a=dx[i]+q[front].x; 34 int b=dy[i]+q[front].y; 35 if(a>=0&&a<=4&&b>=0&&b<=4) 36 { 37 if(map[a][b]==0) 38 { 39 q[pen].x=a; 40 q[pen].y=b; 41 q[pen].pre=front; 42 map[a][b]=1; 43 pen++; 44 } 45 if(a==4&&b==4) 46 print(pen-1); 47 } 48 else 49 continue; 50 } 51 front++; 52 } 53 } 54 55 int main() 56 { 57 for(int i=0;i<5;i++) 58 { 59 for(int j=0;j<5;j++) 60 cin>>map[i][j]; 61 } 62 63 bfs(); 64 65 return 0; 66 }
L. HDU 1241 Oil Deposits
这道题体现了 dfs 算法的递归思想，代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 5 using namespace std; 6 7 int n,m; 8 int g[105][105]; 9 int t[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; 10 11 void dfs(int x,int y) 12 { 13 g[x][y]=0; 14 for(int i=0;i<8;i++) 15 { 16 int a,b; 17 a=x+t[i][0]; 18 b=y+t[i][1]; 19 if(a>=0&&a<m&&b>=0&&b<n&&g[a][b]) 20 dfs(a,b); 21 } 22 } 23 24 int main() 25 { 26 while(cin>>m&&m) 27 { 28 cin>>n; 29 for(int i=0;i<m;i++) 30 { 31 for(int j=0;j<n;j++) 32 { 33 char c; 34 cin>>c; 35 if(c=='*') 36 g[i][j]=0; 37 if(c=='@') 38 g[i][j]=1; 39 } 40 } 41 int num=0; 42 for(int i=0;i<m;i++) 43 { 44 for(int j=0;j<n;j++) 45 { 46 if(g[i][j]) 47 { 48 dfs(i,j); 49 num++; 50 } 51 } 52 } 53 cout<<num<<endl; 54 } 55 return 0; 56 }
M. HDU 1495 非常可乐
bfs 水题，代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<queue> 7 8 using namespace std; 9 10 struct node 11 { 12 int x,y,z; 13 int count; 14 node(int a=0,int b=0,int c=0,int d=0) 15 { 16 x=a; 17 y=b; 18 z=c; 19 count=d; 20 } 21 }; 22 23 int s,n,m; 24 queue<struct node> t; 25 int visit[105][105][105]; 26 27 int min(int x,int y) 28 { 29 return x>y?y:x; 30 } 31 32 void bfs() 33 { 34 while(!t.empty()) 35 t.pop(); 36 memset(visit,0,sizeof(visit)); 37 t.push(node(s,0,0,0)); 38 visit[s][0][0]=1; 39 40 while(!t.empty()) 41 { 42 struct node a; 43 a=t.front(); 44 t.pop(); 45 if(a.x==s/2&&a.y==s/2||a.x==s/2&&a.z==s/2||a.y==s/2&&a.z==s/2) 46 { 47 48 cout<<a.count<<endl; 49 return; 50 } 51 if(a.x!=0) 52 { 53 if(a.y!=n) 54 { 55 int p=min(n-a.y,a.x); 56 if(!visit[a.x-p][a.y+p][a.z]) 57 { 58 struct node temp(a.x-p,a.y+p,a.z,a.count+1); 59 visit[a.x-p][a.y+p][a.z]=1; 60 t.push(temp); 61 } 62 } 63 if(a.z!=m) 64 { 65 int p=min(m-a.z,a.x); 66 if(!visit[a.x-p][a.y][a.z+p]) 67 { 68 struct node temp(a.x-p,a.y,a.z+p,a.count+1); 69 visit[a.x-p][a.y][a.z+p]=1; 70 t.push(temp); 71 } 72 } 73 } 74 if(a.y!=0) 75 { 76 if(a.x!=s) 77 { 78 int p=min(s-a.x,a.y); 79 if(!visit[a.x+p][a.y-p][a.z]) 80 { 81 struct node temp(a.x+p,a.y-p,a.z,a.count+1); 82 visit[a.x+p][a.y-p][a.z]=1; 83 t.push(temp); 84 } 85 } 86 if(a.z!=m) 87 { 88 int p=min(m-a.z,a.y); 89 if(!visit[a.x][a.y-p][a.z+p]) 90 { 91 struct node temp(a.x,a.y-p,a.z+p,a.count+1); 92 visit[a.x][a.y-p][a.z+p]=1; 93 t.push(temp); 94 } 95 } 96 } 97 if(a.z!=0) 98 { 99 if(a.x!=s) 100 { 101 int p=min(s-a.x,a.z); 102 if(!visit[a.x+p][a.y][a.z-p]) 103 { 104 struct node temp(a.x+p,a.y,a.z-p,a.count+1); 105 visit[a.x+p][a.y][a.z-p]=1; 106 t.push(temp); 107 } 108 } 109 if(a.y!=n) 110 { 111 int p=min(n-a.y,a.z); 112 if(!visit[a.x][a.y+p][a.z-p]) 113 { 114 struct node temp(a.x,a.y+p,a.z-p,a.count+1); 115 visit[a.x][a.y+p][a.z-p]=1; 116 t.push(temp); 117 } 118 } 119 } 120 } 121 cout<<"NO"<<endl; 122 return; 123 } 124 125 126 127 int main() 128 { 129 while(scanf("%d%d%d",&s,&n,&m)!=EOF&&s&&m&&n) 130 { 131 if(s%2==1) 132 { 133 cout<<"NO"<<endl; 134 continue; 135 } 136 bfs(); 137 } 138 return 0; 139 }
N. HDU 2612 Find a way
两遍 bfs 即可，代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<queue> 7 8 using namespace std; 9 10 struct node 11 { 12 int x; 13 int y; 14 int time; 15 node(int a=0,int b=0,int c=0) 16 { 17 x=a; 18 y=b; 19 time=c; 20 } 21 }; 22 23 int n,m,yx,yy,mx,my,num; 24 char road[205][205]; 25 int yt[205][205],mt[205][205],visit[205][205]; 26 int t[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 27 queue<struct node> q; 28 29 void bfs() 30 { 31 memset(yt,0,sizeof(yt)); 32 memset(visit,0,sizeof(visit)); 33 while(!q.empty()) 34 q.pop(); 35 q.push(node(yx,yy,0)); 36 visit[yx][yy]=1; 37 int k=0; 38 while(!q.empty()) 39 { 40 struct node w; 41 w=q.front(); 42 q.pop(); 43 for(int i=0;i<4;i++) 44 { 45 int a,b,c; 46 a=w.x+t[i][0]; 47 b=w.y+t[i][1]; 48 c=w.time+1; 49 if(a>=0&&a<n&&b>=0&&b<m&&!visit[a][b]&&road[a][b]!='#') 50 { 51 q.push(node(a,b,c)); 52 visit[a][b]=1; 53 if(road[a][b]=='@') 54 { 55 k++; 56 yt[a][b]=c; 57 } 58 } 59 } 60 if(k==num) 61 break; 62 } 63 64 memset(mt,0,sizeof(mt)); 65 memset(visit,0,sizeof(visit)); 66 while(!q.empty()) 67 q.pop(); 68 q.push(node(mx,my,0)); 69 visit[mx][my]=1; 70 k=0; 71 while(!q.empty()) 72 { 73 struct node w; 74 w=q.front(); 75 q.pop(); 76 for(int i=0;i<4;i++) 77 { 78 int a,b,c; 79 a=w.x+t[i][0]; 80 b=w.y+t[i][1]; 81 c=w.time+1; 82 if(a>=0&&a<n&&b>=0&&b<m&&!visit[a][b]&&road[a][b]!='#') 83 { 84 q.push(node(a,b,c)); 85 visit[a][b]=1; 86 if(road[a][b]=='@') 87 { 88 k++; 89 mt[a][b]=c; 90 } 91 } 92 } 93 if(k==num) 94 break; 95 } 96 } 97 98 int main() 99 { 100 while(scanf("%d%d",&n,&m)!=EOF) 101 { 102 num=0; 103 for(int i=0;i<n;i++) 104 { 105 getchar(); 106 for(int j=0;j<m;j++) 107 { 108 scanf("%c",&road[i][j]); 109 if(road[i][j]=='@') 110 num++; 111 if(road[i][j]=='Y') 112 { 113 yx=i; 114 yy=j; 115 } 116 if(road[i][j]=='M') 117 { 118 mx=i; 119 my=j; 120 } 121 } 122 } 123 bfs(); 124 int cost=n*m; 125 for(int i=0;i<n;i++) 126 { 127 for(int j=0;j<m;j++) 128 { 129 if(yt[i][j]>0) 130 { 131 yt[i][j]=yt[i][j]+mt[i][j]; 132 if(cost>yt[i][j]) 133 cost=yt[i][j]; 134 } 135 } 136 } 137 printf("%d ",cost*11); 138 } 139 return 0; 140 }