1.迷宫问题 题目链接：https://ac.nowcoder.com/acm/problem/14572 来源：牛客网
#include<bits/stdc++.h> using namespace std; char mp[1005][1005]; int n,m,ax,ay,bx,by,vis[1005][1005]; struct su{ int x,y; }; int dx[4]={-1,0,1,0};//上,右,下,左 int dy[4]={0,1,0,-1}; int main() { while(cin>>n>>m){ memset(vis,0,sizeof(vis)); memset(mp,0,sizeof(mp)); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mp[i][j]; if(mp[i][j]=='S'){ax=i;ay=j;} } } queue<su> q; su s1; s1.x=ax;s1.y=ay; q.push(s1); vis[ax][ay]=1; int ans=-1; while(!q.empty()){ su p=q.front();q.pop(); int x=p.x,y=p.y; if(mp[x][y]=='E'){ ans=1;break;} for(int i=0;i<4;i++){ int tx=x+dx[i],ty=y+dy[i]; if(tx < 1 || tx > n || ty < 1 || ty > m || mp[tx][ty] == '#') continue; if(vis[tx][ty]==0){ su s2; vis[tx][ty]=1; s2.x=tx;s2.y=ty; q.push(s2); } } } if(ans==-1) cout<<"No\n"; else cout<<"Yes\n"; } return 0; }2.小妈妈找蝌蚪
题目链接：https://ac.nowcoder.com/acm/problem/14663 题目大意：青蛙妈妈回到家时，发现孩子走丢了。池塘里有很多石头，青蛙家在其中标号为s的石头上。小蝌蚪会移动k分钟，每分钟会出现在任意石头边，甚至多次出现在一块石头边。但k分钟之后，蝌蚪就游不动了。青蛙妈妈第0秒从家所在的石头出发，每分钟移动一次，可以留在原地，也可以跳跃到一块当前可跳跃到的石头上(只能在特定的石头间双向跳跃)。 问：青蛙妈妈最少几分钟发现蝌蚪宝宝 分析：即求出青蛙起点到任一点的最短时间
#include<bits/stdc++.h> using namespace std; int n,m,k,s; const int N=100005; int a[N],vis[N],x,y; vector<int> v[N];//用于储存联通表信息 queue<pair<int,int> > q; void bfs(){ memset(vis,0,sizeof(vis));//同v[] while(q.size()) q.pop();// 同v[] vis[s]=1;//标记家的位置 q.push(make_pair(s,0));//家的位置就是起点 for(int i=1;i<=N;i++){//i表示现在是第几分钟 while(q.size()){ pair<int,int> x1=q.front(); if(x1.second==i) break; // i时间只能走i次 q.pop();//它的位置很关键 int l=v[x1.first].size();//一个石头和几块石头联通 for(int j=0;j<l;j++){ int y1=v[x1.first][j]; if(vis[y1]) continue; vis[y1]=1;//标记 q.push(make_pair(y1,x1.second+1)); } } if(vis[a[min(i,k)]]) {//a[min(i,k)]:小蝌蚪的位置 cout<<i<<endl; return; } } } int main() { while(cin>>n>>m>>k>>s){ for(int i=1;i<=k;i++) cin>>a[i]; for(int i=1;i<=n;i++) v[i].clear();//memset(v,0,sizeof(v));//因为是多组输入，所以每次都要初始化一次 for(int i=1;i<=m;i++) { cin>>x>>y; //建立联通表 v[x].push_back(y);//在v[x]数组的末尾加入y v[y].push_back(x);//在v[y]数组的末尾加入x } bfs(); } return 0; }3.老子的意大利炮呢 题目链接：https://ac.nowcoder.com/acm/problem/15123
#include<bits/stdc++.h> using namespace std; int n,m,k,s,vis[105][105]; int t1,t2,t3; int dx[4]={0,1,0,-1};//右下左上 int dy[4]={1,0,-1,0}; struct su{ int x,y; }; char mp[105][105]; queue <su> q; int bfs(su a,su b){ int t1=-1; while(q.size()) q.pop(); memset(vis,0,sizeof(vis)); q.push(a); vis[a.x][a.y]=1; while(!q.empty()){ int num=q.size(); t1++; while(num--){ su p=q.front();q.pop(); int x=p.x,y=p.y; if(x==b.x&&y==b.y) return t1; for(int i=0;i<4;i++){ int tx=x+dx[i],ty=y+dy[i]; if(tx<1||tx>n||ty<1||ty>m) continue; if(!vis[tx][ty]){ vis[tx][ty]=1; su c; c.x=tx;c.y=ty; q.push(c); } } } } return 0; } int bfs1(su a,su b){ int t1=-1; while(q.size()) q.pop(); memset(vis,0,sizeof(vis)); q.push(a); vis[a.x][a.y]=1; while(!q.empty()){ int num=q.size(); t1++; while(num--){ su p=q.front();q.pop(); int x=p.x,y=p.y; if(x==b.x&&y==b.y) return t1; for(int i=0;i<4;i++){ int tx=x+dx[i],ty=y+dy[i]; if(tx<1||tx>n||ty<1||ty>m||mp[tx][ty] == '#') continue; if(!vis[tx][ty]){ vis[tx][ty]=1; su c; c.x=tx;c.y=ty; q.push(c); } } } } return -1; } int main() { cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mp[i][j]; } } int sx,sy,x1,y1,x2,y2,x3,y3,ex,ey; cin>>sx>>sy>>x1>>y1>>x2>>y2>>x3>>y3>>ex>>ey; cin>>t1>>t2>>t3; su s,s1,s2,s3,e; s.x=sx;s.y=sy;e.x=ex;e.y=ey; s1.x=x1;s1.y=y1; s2.x=x2;s2.y=y2; s3.x=x3;s3.y=y3; int t[9],l[6]; t[0]=bfs(s,s1); t[1]=bfs(s,s2); t[2]=bfs(s,s3); t[3]=bfs(s1,s2); t[4]=bfs(s1,s3); t[5]=bfs(s2,s3); t[6]=bfs1(s1,e); t[7]=bfs1(s2,e); t[8]=bfs1(s3,e); if(t[8]!=-1){ l[0]=t[0]+t[3]*(t1+1)+(t1+t2+1)*t[5]+t[8]*(t1+t2+t3+1); l[1]=t[1]+t[3]*(t2+1)+(t1+t2+1)*t[4]+t[8]*(t1+t2+t3+1); } else{ l[0]=1e7; l[1]=1e7; } if(t[7]!=-1){ l[2]=t[0]+t[4]*(t1+1)+(t1+t3+1)*t[5]+t[7]*(t1+t2+t3+1); l[3]=t[2]+t[4]*(t3+1)+(t1+t3+1)*t[3]+t[7]*(t1+t2+t3+1); } else{ l[2]=1e7; l[3]=1e7; } if(t[6]!=-1){ l[4]=t[1]+t[5]*(t2+1)+(t2+t3+1)*t[4]+t[6]*(t1+t2+t3+1); l[5]=t[2]+t[5]*(t3+1)+(t2+t3+1)*t[3]+t[6]*(t1+t2+t3+1); } else{ l[4]=1e7; l[5]=1e7; } sort(l,l+6); // for(int i=0;i<6;i++) cout<<l[0]<<endl; return 0; }5.相遇问题（双向bfs） 题目链接：https://ac.nowcoder.com/acm/problem/23486 来源：牛客网
题目大意：A与B两人都被困在了迷宫里。A每次可以移动一个位置，而B每次可以移动两次位置，A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，无法相遇，输出”NO"。
#include <bits/stdc++.h> using namespace std; char mp[1005][1005]; int n,m,vis[2][1005][1005]; int ax, ay, bx, by; struct u{ int x,y; }; queue<u> q[2]; int dx[8]={-1,0,1,0,-1,1,1,-1};//上,右,下,左,右上,右下,左下,左上 int dy[8]={0,1,0,-1,1,1,-1,-1}; int bfs(int U) { u u3; int num = q[U].size();//队中元素个数 while(num--){ u p = q[U].front();//得到队首元素 q[U].pop();//取出队首元素 int x=p.x,y=p.y;//记录此时的位置 for(int i = 0; i < 4+(U^1 ? 4 : 0); i++){//a就是8个方向，b就是4个方向 int tx = x+dx[i], ty = y+dy[i]; if(tx < 1 || tx > n || ty < 1 || ty > m || mp[tx][ty] == '#') continue;//不能走的 if(!vis[U][tx][ty]){//判断是否被标记 if(vis[U^1][tx][ty]) return 1;//判断两人是否相遇 vis[U][tx][ty] = 1;//标记 u3.x=tx;u3.y=ty; q[U].push(u3); } } } return 0; } int main() { cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mp[i][j]; if(mp[i][j]=='C') {ax=i;ay=j;}//记录A的位置 if(mp[i][j]=='D') {bx=i;by=j;}//记录B的位置 } } int ans=-1; int t=0; u u1,u2; u1.x=ax;u1.y=ay; u2.x=bx;u2.y=by; q[0].push(u1); q[1].push(u2); vis[0][ax][ay]=vis[1][bx][by]=1;//记录开始位置 while(!q[0].empty()||!q[1].empty()){ t++; if(bfs(0)) {ans=t;break; } if(bfs(1)) {ans=t;break; }//因为B每次可以移动两次位置,也可以移动一次 if(bfs(1)) {ans=t;break; } } if(ans==-1) cout<<"NO\n"; else cout<<"YES\n"<<ans; return 0; }