前一阵子搞教材和其他事情,把博客给落下了。最近趁着找题目的机会,再争取多记录点博客题目。
每日一题最近不能按顺序了,找题目优先了。只能先这样了。
题目描述:
有两个人分别地图上的两个位置,现在两个人要相遇,问最短时间。一个人走8个方向每次一步,另一个走4个方向每次两步。(n,m<=1000)
思路:
经典bfs问题。
两个人相遇问题,显然一个比较常用的方法是离线处理。
先bfs第一个人,记录下他到每个点的最少时间。
接着bfs第二个人,也记录到每个点的最少时间。
那么如果两人能在某个点相遇,相遇时间就是两人中时间大的那个。最后枚举所有的点,找一个最小的值。
注意走两步的处理,在下面的代码中我处理成了走一步花0.5秒,最后计算的时候向上取整。
代码:
#include<bits/stdc++.h> using namespace std; int n,m,v[2][1003][1002]; double d[2][1003][1004],pd; char s[1004][1004]; pair<int,int>p[2]; int dir[][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1}; struct node{ int x,y; double step; }; bool check(int a,int b){ if(s[a][b]=='#')return false; return true; } void bfs(int w){ queue<node>qu; node tmp; tmp.x=p[w].first;tmp.y=p[w].second; tmp.step=0; qu.push(tmp); v[w][tmp.x][tmp.y]=1; while(qu.size()){ node now=qu.front(); qu.pop(); for(int i=0;i<(w?4:8);i++){ node tmp; tmp.x=now.x+dir[i][0]; tmp.y=now.y+dir[i][1]; tmp.step=now.step+1; if(w){ tmp.x=now.x+dir[i][0]; tmp.y=now.y+dir[i][1]; tmp.step=now.step+0.5; } if(s[tmp.x][tmp.y]=='#')continue; if(v[w][tmp.x][tmp.y])continue; v[w][tmp.x][tmp.y]=1; d[w][tmp.x][tmp.y]=tmp.step; qu.push(tmp); } } } int main() { cin>>n>>m; getchar(); for(int i=1;i<=n;i++){ string ts; getline(cin,ts); int cnt=0; for(int j=0;j<ts.size();j++){ if(ts[j]!=' ')s[i][++cnt]=ts[j]; } } for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ if(i==0||j==0||i==n+1||j==m+1)s[i][j]='#'; if(s[i][j]=='C')p[0]=make_pair(i,j); if(s[i][j]=='D')p[1]=make_pair(i,j); } } bfs(0); bfs(1); int ans=1e7+7; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s[i][j]=='#')continue; if(!v[0][i][j]||!v[1][i][j])continue; ans=min(ans,max(int(d[0][i][j]),int(d[1][i][j]+0.5))); } } if(ans==1e7+7)cout<<"NO"<<endl; else cout<<"YES"<<endl<<ans<<endl; return 0; }
方法二:
用双向广搜。双向广搜思路是从两个地方分别开始广搜,每次只扩展一层。然后判断是否能在当前层相遇,如果相遇了就可以退出了。这里处理两步的做法是分成2次1步走,扩展到同一层。即做第二个人每次做2次bfs。
代码:
#include<bits/stdc++.h> using namespace std; int n,m,v[2][1003][1002]; double d[2][1003][1004]; char s[1004][1004]; pair<int,int>p[2]; int dir[][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1}; struct node{ int x,y; double step; }; bool check(int a,int b){ if(s[a][b]=='#')return false; return true; } queue<node>q1,q2; int main() { cin>>n>>m; getchar(); for(int i=1;i<=n;i++){ string ts; getline(cin,ts); int cnt=0; for(int j=0;j<ts.size();j++){ if(ts[j]!=' ')s[i][++cnt]=ts[j]; } } for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++){ if(i==0||j==0||i==n+1||j==m+1)s[i][j]='#'; if(s[i][j]=='C')p[0]=make_pair(i,j); if(s[i][j]=='D')p[1]=make_pair(i,j); } } node tmp; tmp.x=p[0].first;tmp.y=p[0].second; v[0][tmp.x][tmp.y]=1; q1.push(tmp); tmp.x=p[1].first;tmp.y=p[1].second; v[1][tmp.x][tmp.y]=1; q2.push(tmp); int timi=0; int flag=0; while(!flag){ timi++; int cur1,cur2; cur1=q1.size(); cur2=q2.size(); if(cur1==0&&cur2==0){ flag=-1; break; } while(q1.size()&&cur1--){ node now=q1.front(); q1.pop(); for(int i=0;i<8;i++){ node tmp; tmp.x=now.x+dir[i][0];tmp.y=now.y+dir[i][1]; if(v[1][tmp.x][tmp.y]){ flag=1;break; } if(check(tmp.x,tmp.y)&&!v[0][tmp.x][tmp.y]){ v[0][tmp.x][tmp.y]=1; q1.push(tmp); } } } while(q2.size()&&cur2--){ node now=q2.front(); q2.pop(); for(int i=0;i<4;i++){ node tmp; tmp.x=now.x+dir[i][0];tmp.y=now.y+dir[i][1]; if(v[0][tmp.x][tmp.y]){ flag=true; break; } if(v[0][tmp.x][tmp.y]){ flag=1;break; } if(check(tmp.x,tmp.y)&&!v[1][tmp.x][tmp.y]){ v[1][tmp.x][tmp.y]=1; q2.push(tmp); } } } if(flag==1)break; cur2=q2.size(); while(q2.size()&&cur2--){ node now=q2.front(); q2.pop(); for(int i=0;i<4;i++){ node tmp; tmp.x=now.x+dir[i][0];tmp.y=now.y+dir[i][1]; if(v[0][tmp.x][tmp.y]){ flag=true; break; } if(check(tmp.x,tmp.y)&&!v[1][tmp.x][tmp.y]){ v[1][tmp.x][tmp.y]=1; q2.push(tmp); } } } } if(flag==-1)cout<<"NO"<<endl; else { cout<<"YES"<<endl<<timi<<endl; } return 0; }