#include
#include
const int MAX=25;
using namespace std;
typedef struct p
{
int x,y;
int step;
}P;
char map[MAX][MAX];
int mark[MAX][MAX];
int visited[MAX][MAX][MAX][MAX];
int dir1[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//上,右,下,左
int dir2[4][2]={{1,0},{0,-1},{-1,0},{0,1}};//下,左,上,右
int n,m;
P z,s,cur,pre,cur2,pre2;
int check()//判断是否遇见
{
if(cur.x==cur2.x && cur.y==cur2.y)//处于相同位置
return 1;//遇见
for(int i=0;i<4;i++)
{
if(cur.x+dir1[i][0]==cur2.x && cur.y+dir1[i][1]==cur2.y)//邻接
return 1;
}
return 0;
}
int bfs(int x1,int y1,int x2,int y2)
{
z.x=x1,z.y=y1;
s.x=x2,s.y=y2;
queue Q;
visited[x1][y1][x2][y2]=1;
z.step=0;//步数为0
Q.push(z);
Q.push(s);
while(!Q.empty())
{
pre=Q.front();
Q.pop();
cur=pre;
pre2=Q.front();
Q.pop();
cur2=pre2;
for(int i=0;i<4;i++)
{
cur.x=pre.x+dir1[i][0];
cur.y=pre.y+dir1[i][1];
cur2.x=pre2.x+dir2[i][0];//s走
cur2.y=pre2.y+dir2[i][1];//s走
if(map[cur2.x][cur2.y]!='.' || cur2.x<1 || cur2.x>n || cur2.y<1 || cur2.y>m )
{
cur2.x=pre2.x;
cur2.y=pre2.y;
}
if(visited[cur.x][cur.y][cur2.x][cur2.y]==0 && map[cur.x][cur.y]=='.'
&& cur.x>=1 && cur.x<=n && cur.y>=1 && cur.y<=m)
{
cur.step=pre.step+1;
if(check())
{
return cur.step;//返回步数
}
Q.push(cur);
Q.push(cur2);
visited[cur.x][cur.y][cur2.x][cur2.y]=1;
}
}
}
return -1;
}
void init()
{
memset(mark,0,sizeof(mark));
memset(map,0,sizeof(map));
memset(visited,0,sizeof(visited));
}
int main(void)
{
while(scanf("%d%d",&n,&m)==2)
{
int i,j,x1,y1,x2,y2;
init();
//getchar();
for(i=1;i<=n;i++)
{
scanf("%s",map[i]+1);
//gets(map[i]+1);
for(j=1;j<=m;j++)
{
if(map[i][j]=='Z')
{
x1=i,y1=j;
map[i][j]='.';
}
if(map[i][j]=='S')
{
x2=i,y2=j;
map[i][j]='.';
}
}
}
int ans=bfs(x1,y1,x2,y2);
if(ans==-1)
cout<<"Bad Luck!"<
HDU2216_GameIII_暴力广搜
题目大意:
一个男的Z要去找一个女的S,然后这个男的每走一步,那个女的就走跟他相反的方向。这个地图里面只有两种元素,“X”就是墙,“.”就是平地。然后要求这个男的走最少的步数找到女的,相邻或者重合即算找到。
解题思路:
直接用广搜,搜到的第一个就是最短路径啦,(广搜按层搜索的优势),题目中要注意,每走一步,男的跟女的都有状态,而且可能状态还不一样,所以要开个四维的visited数组用来标记他们两个当前的位置是否已经走过了,这个一开始囧了好久好久,想当然地只开了男的的状态……结果答案一直不对。
吐吐槽:
感觉广搜的难点还是要找要标志的状态,比如说走过的点要不要标志掉之类的问题^。^,嘿嘿!慢慢玩咯!
代码: