分析
一些闲话
这里给自己提个醒，看一个题目时，如果只是听人讲明白了，或者看题解看明白了。那隔一段时间后一定要再重新写写，不然就可能像这次，噩梦与小A与小B一样，但有一些细节，当时写噩梦的时候根本没有记在心里。
这次就着重说一下这两道题解决时的共同点。
解决的都是，两个人在迷宫中相遇的最短步数，但是两人在一秒内走的步数不相同的问题
鉴于第一个写的源题目是噩梦，那就管它叫见鬼模型吧
解决思路
这种题目，一定要同时搜索两人，类似双向广搜。
步骤：
-
记录下两人的位置，在搜索时将两人分别放入两个队列
-
重点，我们在处理两人的拓展时，我们假设A 1s 可以a步，B 1s 可以走b步，那我们进行拓展时，要一步一步进行。就是每次处理队列中所有元素，每次只拓展一不，总共进行对应步数。
int bfs() { queue<PII> qa,qb; qa.push(a),qb.push(b); st[a.x][a.y]=1,st[b.x][b.y]=2; int step=0; while(qa.size()||qb.size()) { step++; for(int i=0;i<b;i++) for(int j=0,len=qb.size();j<len;j++) { auto t =qb.front(); qb.pop(); for(int k=0;k<4;k++) { int nx = t.x + dx[k],ny = t.y + dy[k]; if(check()) continue;//不合法情况，直接跳过 if(st[nx][ny]==1) return step;//若是这个点已经有另一个点了，就这直接返回 st[nx][ny]=2; qb.push({nx,ny}); } } for(int i=0;i<1;i++) for(int j=0,len=qa.size();j<len;j++) { auto t =qa.front(); qa.pop(); for(int k=0;k<8;k++) { int nx = t.x + dx[k],ny = t.y + dy[k]; if(check(nx,ny)) continue; if(st[nx][ny]==2) return step; st[nx][ny]=1; qa.push({nx,ny}); } } } return -1; } -
最后根据bfs返回的值，进行判断是否有解
ACcode
小A与小B
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define x first
#define y second
const int N = 1010;
char g[N][N];
int st[N][N];
PII a,b;
int n,m;
int dx[8]={0,0,1,-1,1,1,-1,-1},dy[8]={1,-1,0,0,1,-1,1,-1};
int bfs()
{
queue<PII> qa,qb;
qa.push(a),qb.push(b);
st[a.x][a.y]=1,st[b.x][b.y]=2;
int step=0;
while(qa.size()||qb.size())
{
step++;
for(int i=0;i<2;i++)
for(int j=0,len=qb.size();j<len;j++)
{
auto t =qb.front();
qb.pop();
for(int k=0;k<4;k++)
{
int nx = t.x + dx[k],ny = t.y + dy[k];
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(g[nx][ny]=='#') continue;
if(st[nx][ny]==2) continue;
if(st[nx][ny]==1) return step;
st[nx][ny]=2;
qb.push({nx,ny});
}
}
for(int j=0,len=qa.size();j<len;j++)
{
auto t =qa.front();
qa.pop();
for(int k=0;k<8;k++)
{
int nx = t.x + dx[k],ny = t.y + dy[k];
if(nx<0||nx>=n||ny<0||ny>=m) continue;
if(g[nx][ny]=='#') continue;
if(st[nx][ny]==1) continue;
if(st[nx][ny]==2) return step;
st[nx][ny]=1;
qa.push({nx,ny});
}
}
}
return -1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<2*m;j++)
{
if(j&1) scanf("%c",&g[i][j/2]);
else getchar();
if(g[i][j/2]=='C')
a={i,j/2};
else if(g[i][j/2]=='D')
b={i,j/2};
}
int t = bfs();
if(t==-1) puts("NO");
else
{
puts("YES");
printf("%d\n",t);
}
return 0;
}
噩梦
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 810;
int n,m;
char g[N][N];
int st[N][N];
PII boy,girl,ghost[2];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool check(int a,int b,int step)
{
if(a<0||a>=n||b<0||b>=m||g[a][b]=='X') return false;
for(int i=0;i<2;i++)
if(abs(a-ghost[i].first)+abs(b-ghost[i].second)<=step*2)
return false;
return true;
}
int bfs()
{
int cnt = 0;
memset(st, 0, sizeof st);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(g[i][j]=='M') boy={i,j};
else if(g[i][j]=='G') girl={i,j};
else if(g[i][j]=='Z') ghost[cnt++]={i,j};
int step = 0;
queue<PII> qb,qg;
qb.push(boy),qg.push(girl);
while(qb.size()||qg.size())
{
step++;
for(int i=0;i<3;i++)
for(int j=0,len=qb.size();j<len;j++)
{
auto t = qb.front();
qb.pop();
if(!check(t.first,t.second,step)) continue;
for(int k=0;k<4;k++){
int a = t.first + dx[k],b = t.second + dy[k];
if(!check(a,b,step)) continue;
if(st[a][b]==2) return step;
if(!st[a][b])
{
st[a][b]=1;
qb.push({a,b});
}
}
}
for(int j=0,len=qg.size();j<len;j++)
{
auto t = qg.front();
qg.pop();
if(!check(t.first,t.second,step)) continue;
for(int k=0;k<4;k++){
int a = t.first + dx[k],b = t.second + dy[k];
if(!check(a,b,step)) continue;
if(st[a][b]==1) return step;
if(!st[a][b])
{
st[a][b]=2;
qg.push({a,b});
}
}
}
}
return -1;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",g[i]);
int t = bfs();
printf("%d\n",bfs());
}
return 0;
}