[TJOI2008] Binary Land
题目背景
Binary Land是一款任天堂红白机上的经典游戏,讲述的是两只相爱的企鹅Gurin和Malon的故事。两只企鹅在一个封闭的迷宫中,你可以控制他们向上下左右四个方向移动。但是他们的移动有一个奇怪的规则,即如果你按“上”或“下”方向键,两只企鹅会同时向上移动或向下移动1格;如果你按“左”方向键,则Malon向左移动1格,同时Gurin向右移动1格;如果你按“右”方向键,则Malon向右移动1格,Gurin向左移动1格。当然,如果某只企鹅被障碍挡住,它就不会移动了。另外,在迷宫的某些格子处有蜘蛛网,如果任何一只企鹅进入这种格子,则游戏失败。两只企鹅不会相互阻挡,即在相向运动时他们可以“穿过”彼此,也可以同时处于同一格子里。迷宫的某个格子上有一颗红心,游戏的任务就是使两只企鹅同时到达这个格子。
题目描述
请编写程序找出完成任务所需的最少的操作步数。如果无法完成目标,输出“no”。
输入格式
第一行包含两个整数R, C 表示迷宫的长和宽。
按下来有R行,每行包含C个字符,描述了一个迷宫。其中’#’表示企鹅不能通过的障碍物,’X’表示蜘蛛网,’.’表示空地,’G’表示Gurin的初始位置,’M’表示Malon的初始位置,’T’表示终点位置。
输入数据保证标有’G’,’M’,’T’的格子分别只有一个,保证企鹅不可能走到迷宫以外。
输出格式
输出只有一行,为最少的操作步数。如果不能完成任务,输出“no”。
样例 #1
样例输入 #1
4 7
#######
#..T..#
#G##M##
#######
样例输出 #1
4
提示
满足要求的一个操作序列为:上-右-左-左
3 ≤ R, C ≤ 30
大致思路
!BFS!
根据题目,我们需要兼顾两个点,G与M,其实这与只看一个点时相差无几,用结构体存储即可,对于特殊的移动法则,我们也可以用一个数组存储方位来实现。BFS的判重可以直接用一个四维数组,反正数据范围不大
char sm[66][66];
int n,m;
int agx[]={0,-1,0,1};
int agy[]={-1,0,1,0};
int amx[]={0,-1,0,1};
int amy[]={1,0,-1,0};
struct awsl{
int gx,gy,mx,my,cnt;
};
bool vis[31][31][31][31];
int goalx,goaly;
queue<awsl> q;
bool flag=1;
BFS部分直接套模板就好啦,对于G与M都处于’ # '的点,我们无需让他入队,不移动肯定不会是答案,也不会是最优。若搜索结束还没有搜到,则输出“ no ”
(代码较为繁琐,其实原理是很简单的QAQ)
while(!q.empty()){
awsl tmp,kk;
tmp=q.front();
q.pop();
if(vis[tmp.gx][tmp.gy][tmp.mx][tmp.my]==1)continue;
vis[tmp.gx][tmp.gy][tmp.mx][tmp.my]=1;
if(tmp.gx==tmp.mx&&tmp.gx==goalx&&tmp.gy==tmp.my&&tmp.my==goaly){
cout<<tmp.cnt;
flag=0;
break;
}
for(int i=0;i<4;i++){
int new_gx,new_gy,new_mx,new_my;
new_gx=tmp.gx+agx[i];new_mx=tmp.mx+amx[i];
new_gy=tmp.gy+agy[i];new_my=tmp.my+amy[i];
if(sm[new_gx][new_gy]=='X'||sm[new_mx][new_my]=='X'){
continue;
}
if(sm[new_gx][new_gy]=='#'&&sm[new_mx][new_my]!='#'){
kk.cnt=tmp.cnt+1,kk.gx=tmp.gx,kk.gy=tmp.gy;
kk.mx=new_mx,kk.my=new_my;
q.push(kk);
}
else if(sm[new_gx][new_gy]!='#'&&sm[new_mx][new_my]=='#'){
kk.cnt=tmp.cnt+1,kk.mx=tmp.mx,kk.my=tmp.my;
kk.gx=new_gx,kk.gy=new_gy;
q.push(kk);
}
else if(sm[new_gx][new_gy]!='#'&&sm[new_mx][new_my]!='#'){
kk.cnt=tmp.cnt+1,kk.mx=new_mx,kk.my=new_my;
kk.gx=new_gx,kk.gy=new_gy;
q.push(kk);
}
}
}
if(flag)cout<<"no";
AC CODE
#include<bits/stdc++.h>
using namespace std;
char sm[66][66];
int n,m;
int agx[]={0,-1,0,1};
int agy[]={-1,0,1,0};
int amx[]={0,-1,0,1};
int amy[]={1,0,-1,0};
struct awsl{
int gx,gy,mx,my,cnt;
};
bool vis[31][31][31][31];
int goalx,goaly;
queue<awsl> q;
bool flag=1;
int main(){
cin>>n>>m;
awsl k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>sm[i][j];
if(sm[i][j]=='G'){
k.gx=i;
k.gy=j;
}
if(sm[i][j]=='M'){
k.mx=i;
k.my=j;
}
if(sm[i][j]=='T'){
goalx=i;
goaly=j;
}
}
}
k.cnt=0;
q.push(k);
while(!q.empty()){
awsl tmp,kk;
tmp=q.front();
q.pop();
if(vis[tmp.gx][tmp.gy][tmp.mx][tmp.my]==1)continue;
vis[tmp.gx][tmp.gy][tmp.mx][tmp.my]=1;
if(tmp.gx==tmp.mx&&tmp.gx==goalx&&tmp.gy==tmp.my&&tmp.my==goaly){
cout<<tmp.cnt;
flag=0;
break;
}
for(int i=0;i<4;i++){
int new_gx,new_gy,new_mx,new_my;
new_gx=tmp.gx+agx[i];new_mx=tmp.mx+amx[i];
new_gy=tmp.gy+agy[i];new_my=tmp.my+amy[i];
if(sm[new_gx][new_gy]=='X'||sm[new_mx][new_my]=='X'){
continue;
}
if(sm[new_gx][new_gy]=='#'&&sm[new_mx][new_my]!='#'){
kk.cnt=tmp.cnt+1,kk.gx=tmp.gx,kk.gy=tmp.gy;
kk.mx=new_mx,kk.my=new_my;
q.push(kk);
}
else if(sm[new_gx][new_gy]!='#'&&sm[new_mx][new_my]=='#'){
kk.cnt=tmp.cnt+1,kk.mx=tmp.mx,kk.my=tmp.my;
kk.gx=new_gx,kk.gy=new_gy;
q.push(kk);
}
else if(sm[new_gx][new_gy]!='#'&&sm[new_mx][new_my]!='#'){
kk.cnt=tmp.cnt+1,kk.mx=new_mx,kk.my=new_my;
kk.gx=new_gx,kk.gy=new_gy;
q.push(kk);
}
}
}
if(flag)cout<<"no";
return 0;
}