首页 > 搜索 > BFS搜索 > hdu 1983 Kaitou Kid – The Phantom Thief (2)-DFS-[解题报告]C++
2013
12-26

hdu 1983 Kaitou Kid – The Phantom Thief (2)-DFS-[解题报告]C++

Kaitou Kid – The Phantom Thief (2)

问题描述 :

破解字迷之后,你得知Kid将会在展览开始后T分钟内盗取至少一颗宝石,并离开展馆。整个展馆呈矩形分布,划分为N*M个区域,有唯一的入口和出口(不能从出口进入,同样不能从入口出去)。由某个区域可直接移动至相邻四个区域中的一个,且最快需要一分钟。假设Kid进入放有宝石的区域即可盗取宝石,无需耗时。问至少要封锁几个区域(可以封锁放有宝石的区域,但不能封锁入口和出口)才能保证Kid无法完成任务。

输入:

输入的第一行有一个整数C,代表有C组测试数据。每组测试数据的第一行有三个整数N,M,T(2<=N,M<=8,T>0)。接下来N行M列为展馆布置图,其中包括:

‘S’:入口
‘E’:出口
‘J’:放有宝石的区域,至少出现一次
‘.’:空白区域
‘#’:墙

输出:

输入的第一行有一个整数C,代表有C组测试数据。每组测试数据的第一行有三个整数N,M,T(2<=N,M<=8,T>0)。接下来N行M列为展馆布置图,其中包括:

‘S’:入口
‘E’:出口
‘J’:放有宝石的区域,至少出现一次
‘.’:空白区域
‘#’:墙

样例输入:

2
5 5 5
SJJJJ
..##J
.JJJJ
.J...
EJ...
5 5 6
SJJJJ
..##J
.JJJJ
.J...
EJ...

样例输出:

0
2

思路:

封锁出口或者入口周围的格子.

最多需要4个封锁点.

 

所以我们可以采取这样的策略:

1.寻找一条盗贼的可行路线,如果没有,返回0.

2.计算封锁出口和入口四周需要的封锁点数量,取小的一个,假设是k,k <=4

3.从少到多,遍历所有封锁点个数小于k的方案,验证是否是一条有效的覆盖方案

(可以通过是否阻止了1中的盗贼线路进行快速验证).

如果有有效覆盖方案,返回这个方案的覆盖点值,否则继续.

4.如果没有比k小的覆盖方案,返回k.

 

时间复杂度:

最多(M*N)^3次有效覆盖验证.(8*8)^3=256k.其中有很大一部分可以通过快速验证排除(取决于1的路径长短,所以一般1应该求出最短路径的可行路线)

#include <iostream>

#include <queue>

#include <string>

using namespace std;

int n,m,t,ans;

int dir[4][2] = {1,0,-1,0,0,-1,0,1};

char map[10][10];

bool vis[2][10][10];

struct node

{

   int x,y,t,k;

   int rox[64],roy[64];

};

node start,end,temp,in;

queue <node> Q;

void dfs(int deep)

{

       if(deep > ans) return ;

    int i,j,minstep = -1;

    node q;

    while(!Q.empty())//清空队列

       Q.pop();

       Q.push(start);//起始位置入队

    memset(vis,false,sizeof(vis));//初始化标记数组

       vis[0][start.x][start.y] = true;//标记起始点为真

       while(!Q.empty())//从起点开始寻找一条路径

    {

              q = Q.front();

        Q.pop();

        if(q.t > t) 

                     continue;

        if(q.k && map[q.x][q.y] == 'E')//找到出口

        {

                     minstep = q.t;

                     break;

        }

        for(i = 0;i < 4;i++)//分别从四个方向开始扫描

        {

                     int xx = q.x + dir[i][0];

            int yy = q.y + dir[i][1];

            if(xx < 0 || xx >= n || yy < 0 || yy >= m || map[xx][yy] == '#')

                            continue;//越界或碰到墙

            if(map[xx][yy] == 'J')

                            in.k = 1;//碰到珠宝

            else 

                            in.k = q.k;//没有碰到则标记为前一个状态

            if(!vis[in.k][xx][yy])

            {

                            vis[in.k][xx][yy] = true;

                for(j = 1;j <= q.t;j++)

                {

                                   in.rox[j] = q.rox[j];

                    in.roy[j] = q.roy[j];

                }

                            in.x = xx;

                            in.y = yy;

                            in.t = q.t + 1;

                in.rox[in.t] = xx;

                in.roy[in.t] = yy;

                Q.push(in);

                     }

              }

       }

    if(minstep == -1)

    {// minstep == -1 表明在t时间内即使不用设置关卡也不能成功逃离

              if(deep < ans)

                     ans = deep;

        return ;

    }

       char cc;

    for(i = 1;i < q.t;i++)

    {

              cc = map[q.rox[i]][q.roy[i]];

              if(cc == 'S' || cc == 'E') 

                     continue;

              map[q.rox[i]][q.roy[i]] = '#';

              dfs(deep+1);

              map[q.rox[i]][q.roy[i]] = cc ;

       }

}

void inits()

{

       int i,j;

    memset(vis,false,sizeof(vis));

    for(i = 0;i < n;i++)

              for(j = 0;j < m;j++)

              {

                     if(map[i][j] == 'S')

                     {

                            start.x = i;start.y = j;

                            start.t = 0;start.k = 0;

                            break;

                     }

              }

    ans = 4;

    dfs(0);

    printf("%d/n",ans);

}

int main()

{

       int i,cas;

    scanf("%d",&cas);

    while(cas--)

    {

              scanf("%d%d%d",&n,&m,&t);

        for(i = 0;i < n;i++)

           scanf("%s",map[i]);

        inits();

    }

    return 0;

}

解题转自:http://blog.csdn.net/zxddavy/article/details/6257349


, ,
  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?

  2. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!