C++ 代码
#include<iostream>
#include<algorithm>
#include<deque>
#include<cstring>
#include<utility>
using namespace std;
using pii=pair<int,int>;
char grid[801][801];
int used[801][801];///1表示鬼,2表示男孩,3表示女孩
int n,m;
int gs;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
inline bool is_ok(int i,int j)
{
if(i>=0 && i<n && j>=0 && j<m)
return true;
return false;
}
void ghost_bfs(deque<pii> &deq)
{
int len=deq.size();
int cnt=0;
int i,tr,tc;
int r,c;
while(cnt++<len)
{
auto p=deq.front();
deq.pop_front();
r=p.first,c=p.second;
for(i=0;i<4;++i)
{
tr=r+dx[i];
tc=c+dy[i];
if(is_ok(tr,tc) && used[tr][tc]!=1)
{
used[tr][tc]=1;
deq.push_back({tr,tc});
}
}
}
}
bool people_bfs(deque<pii> &deq)
{
int len=deq.size();
int cnt=0;
int r,c;
int i,tr,tc;
while(cnt++<len)
{
auto p=deq.front();
deq.pop_front();
r=p.first,c=p.second;
if(used[r][c]==1)continue;
for(i=0;i<4;++i)
{
tr=r+dx[i];
tc=c+dy[i];
if(is_ok(tr,tc) && grid[tr][tc]!='X' && used[tr][tc]!=1)
{
if(used[tr][tc])
{
///要么为2,要么为3
if(used[tr][tc]!=used[r][c])return true;
}
else
{
used[tr][tc]=used[r][c];
deq.push_back({tr,tc});
}
}
}
}
return false;
}
int bfs()
{
int step=0;
gs=0;
deque<pii> boy;
deque<pii> girl;
deque<pii> ghost;
int i,j;
for(i=0;i<n;++i)
{
for(j=0;j<m;++j)
{
if(grid[i][j]=='M')
boy.push_back({i,j}),used[i][j]=2;
else if(grid[i][j]=='G')
girl.push_back({i,j}),used[i][j]=3;
else if(grid[i][j]=='Z')
ghost.push_back({i,j}),used[i][j]=1;
}
}
while(boy.size() && girl.size())
{
step++;
int k;
for(k=0;k<2;++k)
ghost_bfs(ghost);
for(k=0;k<3;++k)
if(people_bfs(boy))
return step;
if(people_bfs(girl))
return step;
}
return -1;
}
int main()
{
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
cin>>n>>m;
memset(used,0,sizeof used);
int i,j;
for(i=0;i<n;++i)
{
for(j=0;j<m;++j)
cin>>grid[i][j];
}
//cout<<n<<m<<endl;
cout<<bfs()<<endl;
}
return 0;
}