NC23486 小A与小B
小A与小B
https://ac.nowcoder.com/acm/problem/23486
题目大意:
小A和小B被困在里迷宫里的不同位置,小A可以向周围8个方向每次移动一个位置,而小B则可以向周围四个方向每次移动两个位置,问他们最早什么时候能够找到对方,如果他们最终无法相遇,那么就输出”NO"。
输入描述:
第一行两个整数N,M分别表示迷宫的行和列。(1≤n,m≤1000)
接下来一个N*M 的矩阵
其中"C"表示小A的位置,"D"表示小B的的位置,
"#"表示不可通过的障碍,"."则是可以正常通过的位置。字符用空格隔开。
输出描述:
如果可以相遇,第一行输出一个YES,第二行一个整数输出最短的相遇时间。
否则就输出一个NO表示不能相遇。
题目分析:
小A和小B每次可以移动的距离不一样是问题的关键,仔细思考,我们可以将小A每次走一步和两步都以相同的时间表示出来即可将问题解决。这题我的解法是双起点bfs,将小A和小B的起始位置都push进一个队列里面,在往周围走的时候以不同的vis标记来记录小A和小B走过的路径,当小A走到有小B路径标记的点,或者小B走到小A之前的路径时,两人即可最早在此相遇,输出此时花费的时间即可。
#include<iostream> #include<cstdio> #include<vector> #include<cmath> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<map> #include<set> #define endl '\n' #define all(s) s.begin(),s.end() #define lowbit(x) (x&-x) #define rep(i,a,n) for (int i=a;i<=n;i++) #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define mem(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define pb push_back #define pi acos(-1.0) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+7; const double eps=1e-8; const int inf=0x3f3f3f3f; const int N=2e5+10; char mp[1010][1010]; int vis[1010][1010]; int dir[8][2]={0,1,0,-1,1,0,-1,0,1,-1,1,1,-1,1,-1,-1}; //int dir[4][2]={0,1,0,-1,1,0,-1,0}; struct node{ int x,y,k,step; }; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mp[i][j]; } } queue<node>q; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(mp[i][j]=='C') q.push(node{i,j,1,0}),vis[i][j]=1; if(mp[i][j]=='D') q.push(node{i,j,2,0}),vis[i][j]=2; } } while(!q.empty()){ node on=q.front(); q.pop(); if(on.k==1){ for(int i=0;i<8;i++){ int dx=on.x+dir[i][0],dy=on.y+dir[i][1]; if(dx<1||dx>n||dy<1||dy>m||vis[dx][dy]==1||mp[dx][dy]=='#') continue; if(vis[dx][dy]==2){ cout<<"YES"<<endl<<on.step+1; return 0; }else{ vis[dx][dy]=1; q.push(node{dx,dy,1,on.step+1}); } } } if(on.k==2){ for(int i=0;i<4;i++){ int dx=on.x+dir[i][0],dy=on.y+dir[i][1]; if(dx<1||dx>n||dy<1||dy>m||vis[dx][dy]==2||mp[dx][dy]=='#') continue; if(vis[dx][dy]==1){ cout<<"YES"<<endl<<on.step+1; return 0; }else{ vis[dx][dy]=2; q.push(node{dx,dy,2,on.step+1}); } for(int j=0;j<4;j++){ int fx=dx+dir[j][0],fy=dy+dir[j][1]; if(fx<1||fx>n||fy<1||fy>m||vis[fx][fy]==2||mp[fx][fy]=='#') continue; if(vis[fx][fy]==1){ cout<<"YES"<<endl<<on.step+1; return 0; }else{ vis[fx][fy]=2; q.push(node{fx,fy,2,on.step+1}); } } } } } cout<<"NO"; }