首页 > 搜索 > BFS搜索 > HDU 4528-小明系列故事――捉迷藏-BFS-[解题报告]HOJ
2015
07-17

HDU 4528-小明系列故事――捉迷藏-BFS-[解题报告]HOJ

小明系列故事――捉迷藏

问题描述 :

  小明的妈妈生了三个孩子,老大叫大明, 老二叫二明, 老三…, 老三自然就叫小明了。
  一天,小明的妈妈带小明兄弟三人去公园玩耍,公园里面树木很多,有很多地方可以藏身, 于是他们决定玩捉迷藏。经过几轮的猜拳后,第一轮是小明来找其他两个人,游戏规则很简单:
  只要小明可以在规定的时间内找到他们就算小明获胜,并且被发现的两个人猜拳决定谁在下一轮负责找人;如果在规定的时间内只找到一个人,那么没有被发现的人获胜,被找到的人下一轮负责找人;如果在规定的时间内一个人都没有找到,则小明失败了,下一轮还是他来找人。现在小明想知道,在规定时间内,自己是否可以找到所有的人,现在他想请你来帮忙计算一下。
  为了简单起见,把公园看成是n行m列的矩阵,其中’S’表示小明,’D’表示大名,’E’表示二明,’X’表示障碍物,’.’表示通路。这里,我们把发现定义为,可以直接看到对方, 也就是说两个人在同一行或者同一列,并且中间没有障碍物或者没有其他人就可以看到对方。并且假设,大明,二明藏好以后就不会再改变位置,小明每个单位时间可以从当前的位置走到相邻的四个位置之一,并且不会走出公园。

输入:

测试数据第一行是一个正整数T,表示有T组测试数据。
每一组测试数据首先是三个正整数n,m,t,分别表示行数、列数和规定的时间,接下来n行,每行m个上述的字符,并且保证有且只有一个’S’,一个’E’,一个’D’。

[Technical Specification]
T < 200
3 <= n, m <= 100
0 <= t <= 100

输出:

测试数据第一行是一个正整数T,表示有T组测试数据。
每一组测试数据首先是三个正整数n,m,t,分别表示行数、列数和规定的时间,接下来n行,每行m个上述的字符,并且保证有且只有一个’S’,一个’E’,一个’D’。

[Technical Specification]
T < 200
3 <= n, m <= 100
0 <= t <= 100

样例输入:

3
5 6 3
XXD...
....E.
....X.
....S.
......
5 6 3
XDX...
....E.
......
....S.
......
5 6 8
XXDX..
.XEX..
......
....S.
......

样例输出:

Case 1:
-1
Case 2:
3
Case 3:
-1

题目:点击打开链接

宽搜。注意判重。判重导致比赛的时候错了两次。

#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
#include <stack>
#include <deque>
using namespace std;
typedef  __int64 LL;
#define eps 10e-9
#define inf 0x3f3f3f3f
const int maxn = 100+20;
const int mod  = 1000000000+7;
char ma[maxn][maxn];
bool vis[maxn][maxn][2][2];
struct node{
    int x,y,step;
    int f1,f2;
}s_pos,d_pos,e_pos;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int n,m,t;
void cheak(node &a,node b){
     if(a.x==b.x){
         int start=min(a.y,b.y),end=max(a.y,b.y),find=0;
         for(int i=start+1;i<end;i++){
             if(ma[a.x][i]!='.') {
               find=1; break;
             }
         }
         if(!find){
              a.f1=1;
         }
     }
     if(a.y==b.y){
         int start=min(a.x,b.x),end=max(a.x,b.x),find=0;
         for(int i=start+1;i<end;i++){
             if(ma[i][a.y]!='.') {
                find=1; break;
             }
         }
         if(!find){
              a.f1=1;
         }
     }

}
void cheak2(node &a,node b){
     if(a.x==b.x){
         int start=min(a.y,b.y),end=max(a.y,b.y),find=0;
         for(int i=start+1;i<end;i++){
             if(ma[a.x][i]!='.') {
               find=1; break;
             }
         }
         if(!find){
              a.f2=1;
         }
     }
     if(a.y==b.y){
         int start=min(a.x,b.x),end=max(a.x,b.x),find=0;
         for(int i=start+1;i<end;i++){
             if(ma[i][a.y]!='.') {
                find=1; break;
             }
         }
         if(!find){
              a.f2=1;
         }
     }

}
int bfs(){
    memset(vis,false,sizeof(vis));
    queue<node> q;
    cheak(s_pos,d_pos);
    cheak2(s_pos,e_pos);
    vis[s_pos.x][s_pos.y][s_pos.f1][s_pos.f2]=true;

    q.push(s_pos);
    while(!q.empty()){
        node now = q.front();q.pop();
        if(now.f1>0&&now.f2>0){
           return now.step;
        }
        for(int i=0;i<4;i++){
            node next=now;
            next.x+=dx[i];next.y+=dy[i];
            if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&!vis[next.x][next.y][next.f1][next.f2]
               &&ma[next.x][next.y]=='.'){
                  vis[next.x][next.y][next.f1][next.f2]=true;
                  next.step++;
                  if(!next.f1)
                  cheak(next,d_pos);

                  if(!next.f2)
                  cheak2(next,e_pos);
                  if(next.step<=t)
                  q.push(next);

            }
        }
    }
    return 10000;
}
int main(){
    int  T,ca=1;
    cin>>T;
    while(T--){
       scanf("%d %d %d",&n,&m,&t);
       for(int i=0;i<n;i++)
            scanf("%s",ma[i]);

       for(int i=0;i<n;i++){
          for(int j=0;j<m;j++){
             if(ma[i][j]=='S'){
                  s_pos.x=i;s_pos.y=j;
                  s_pos.step=0;
                  s_pos.f1=s_pos.f2=0;
             }
             if(ma[i][j]=='D'){
                 d_pos.x=i;d_pos.y=j;
             }
             if(ma[i][j]=='E'){
                 e_pos.x=i;e_pos.y=j;
             }
          }
       }
       int now=bfs();
       printf("Case %d:\n",ca++);
       if(now<=t) printf("%d\n",now);
       else       printf("-1\n");

    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/w00w12l/article/details/8722775


,
  1. 因为这200年来,中国没有和平,没有稳定,一直在被人欺负。如果楼主还想希望中国不稳定,不和平,那么在未来的200年,甚至很长时间里,中国人依然一事无成,成天就剩下BB了。

  2. 因为这200年来,中国没有和平,没有稳定,一直在被人欺负。如果楼主还想希望中国不稳定,不和平,那么在未来的200年,甚至很长时间里,中国人依然一事无成,成天就剩下BB了。