浙江财经大学
信息管理与工程学院

HDU 2216 Game III(BFS)

本文由 Ocrosoft 于 2016-07-06 22:11:39 发表

Game III

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1615    Accepted Submission(s): 460

Problem Description
Zjt and Sara will take part in a game, named Game III. Zjt and Sara will be in a maze, and Zjt must find Sara. There are some strang rules in this maze. If Zjt move a step, Sara will move a step in opposite direction.
Now give you the map , you shold find out the minimum steps, Zjt have to move. We say Zjt meet Sara, if they are in the same position or they are adjacent . 
Zjt can only move to a empty position int four diraction (up, left, right, down). At the same time, Sara will move to a position in opposite direction, if there is empty. Otherwise , she will not move to any position.
The map is a N*M two-dimensional array. The position Zjt stays now is marked Z, and the position, where Sara stays, is marked E.
>  . : empty position
>  X: the wall
>  Z: the position Zjt now stay
>  S: the position Sara now stay
Your task is to find out the minimum steps they meet each other.
 

Input
The input contains several test cases. Each test case starts with a line contains three number N ,M (2<= N <= 20, 2 <= M <= 20 ) indicate the size of the map. Then N lines follows, each line contains M character. A Z and a S will be in the map as the discription above.
 

Output
For each test case, you should print the minimum steps. “Bad Luck!” will be print, if they can’t meet each other.
 

Sample Input
	
4 4 XXXX .Z.. .XS. XXXX 4 4 XXXX .Z.. .X.S XXXX 4 4 XXXX .ZX. .XS. XXXX
 

Sample Output
	
1 1 Bad Luck!
 

Solution

讲的是S要去找Z,当S移动的时候,Z会往相反的方向移动,如果不能移动就不移动。能否相遇。相遇的意思是,坐标差绝对值和为1(相邻)或者坐标相等(重合)。

跟一般的BFS一样,让S移动,然后让Z移动(如果不能移动就不移动),然后看四维(S和Z的x,y)的vis数组是否访问过。

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
struct point
{
    int x,y;//Z
    int xx,yy;//S
    int step;
    bool check()
    {
        if(abs(x-xx)+abs(y-yy)==1)return 1;
        if(x==xx&&y==yy)return 1;
        return 0;
    }
} s,e,t;
char mp[22][22];
bool vis[22][22][22][22];
int dir[4][2]= {0,1,0,-1,1,0,-1,0};
int n,m;
int bfs()
{
    ms(vis);
    queue<point> q;
    q.push(s);
    while(!q.empty())
    {
        s=q.front();
        q.pop();
        if(s.check())return s.step;
        for(int i=0; i<4; i++)
        {
            t=s,t.x+=dir[i][0],t.y+=dir[i][1],t.step++;
            if(t.x<0||t.y<0||t.x>=n||t.y>=m)continue;
            if(mp[t.x][t.y]=='X')continue;
            t.xx-=dir[i][0],t.yy-=dir[i][1];
            if(t.xx<0||t.yy<0||t.xx>=n||t.yy>=m||mp[t.xx][t.yy]=='X')//如果S不能移动
                t.xx+=dir[i][0],t.yy+=dir[i][1];//取消移动
            if(vis[t.x][t.y][t.xx][t.yy])continue;
            vis[t.x][t.y][t.xx][t.yy]=1;
            q.push(t);
        }
    }
    return -1;
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=0; i<n; i++)cin>>mp[i];
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
                if(mp[i][j]=='Z') s.x=i,s.y=j,s.step=0;
                else if(mp[i][j]=='S') s.xx=i,s.yy=j;
        int ans=bfs();
        if(ans==-1)printf("Bad Luck!\n");
        else printf("%d\n",ans);
    }
    return 0;
}

 

欢迎转载,请保留出处与链接。Ocrosoft » HDU 2216 Game III(BFS)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址