题解 P1374 【进攻幽暗城】

world_execute · 2019-05-05 19:07:14 · 题解

[ 更好的阅读体验 ]

[ 原题面 ]

第零部分 —— 阅读题目

• 题目大意：幽暗城中有三个人，萨尔 Sal ，恐惧魔王 Dread Lord ，And 小A。刚开始，小A与萨尔在 (x1,y1) 位置，而恐惧魔王在 (x2,y2) 位置。小A想要走到恐惧魔王的位置，但不能离萨尔d个单位距离以上超过s秒，同时，萨尔与恐惧魔王都会按照各自的模式，固定的行走。

• 输入：幽暗城的地图，0表示可以走，1表示被挡住，不能走。

• 数据范围：1 \le 地图长、宽 \le 50，0 \le 最大离开时间 \le 1000，0 \le 最大离开距离 \le 100，计算欧几里得距离（直线距离）

• So， O(nm * 答案大小 * 一个非常大的常数) 的算法似乎轻松可以过，而且跑的飞快。

第一部分 —— 开始分析

• 似乎可以用搜索做，但是有好多问题有待解决，如离开时间、每个时间上，萨尔与恐惧魔王的位置，搜索陷入死循环，被困在圈内……

• 可是有什么困难可以阻挡我们AC这道题的脚步呢？我们把这些难点逐个突破，一定可以做出的。

• So，我们初步确定了算法，可以开始着手思考一些细节了。

第三部分 —— 深入思考

• So Good，我们先解决陷入一个死循环。

• 有人会说，为何会进入死循环？那时的情况Looks like this:

           ...1111...
           ...1001...
           ...1000<-.
           ...1001...
           ...1111...

  (从箭头所指处进入，先判断上，所以无法退出）

• And，how to do？我们可以百度搜索：迭代加深搜索。（用力划掉( /ω＼ )）

• 迭代加深搜索（IDDFS）可以有效地避免搜索层数过多，导致的TLE。

• 具体来说迭代加深搜索就是在每次搜索时，限定一个最大搜索层数，每当超过Max_Deep时return，具体实现将会在 第五部分——代码实现 部分具体讲述，不用急，在你看过下面的解析后，可以根据它的定义，不看代码就写出来。

• 所有新知识都讲完了呢ヽ(✿ﾟ▽ﾟ)ノ。（巨佬请无视此句）

• Haha，萨尔的位置与恐惧魔王的位置怎么办呢？预处理呀，利用生成串来预处理，因为他们 （你怎么知道是“他们”而不是“她们”或“它们”的呢） 的位置只与时间有关，和小A的位置无关

• 还有，对于离开的时间如何进行判断？按题意判断就好了呀。（QAQ）

• So，是不是可以开始码代码了呢？我相信你有这个实力，去吧，（关了题解去码吧） 去看下一部分，那里较为详细地讲述了如何代码实现此题。

第五部分 —— 代码实现

• 输入部分：讲一下吧，本人认为这部分有些难度，机房几位巨佬都一不小心写错了呢。

  scanf("%d%d%d%d", &n, &m, &s, &r);  //输入地图大小，最长离开时间，最大光环距离
  for (int i=1; i<=n; ++i)
  for (int j=1; j<=m; ++j)
      cin>>ch,Map[i][j]=(ch-48);  //输入地图
  scanf("%d%d%d%d", &Salx[0], &Saly[0], &Lorx[0], &Lory[0]);  //输入x1,y1,x2,y2
  cin>>st_Sal;    //输入萨尔的位置生成串
  cin>>st_Lor;    //输入恐惧魔王的的位置生成串

• Sal 即 萨尔的英文， Lor 即 Dread Lord的缩写 也就是 恐惧魔王的英文。（举报，有人机房打“Saly” o(￣▽￣)ｄ）

• 然后就是对答案等于0时的预处理

       (Salx[0]==Lorx[0] && Saly[0]==Lory[0])

• 再是对萨尔位置与魔王位置的Preprocessing。

• 这段代码本人写的十分丑陋，但还是放上来吧：

for (int i=1; i<=100; ++i)  //生成100次之内的位置
{
    int tx = Lorx[i-1]+bak[st_Lor[(i-1)%st_Lor.length()]-48];   //Bak即位置预处理数组
    int ty = Lory[i-1]+bak[st_Lor[(i-1)%st_Lor.length()]-43];   //此时减去43是因为在减48的同时要加5，因为这是对y坐标的更改，不能和x坐标混淆
    if ((tx<1)||(tx>n)||(ty<1)||(ty>m)) //走出边界
        tx = Lorx[i-1],ty = Lory[i-1];
    else if (Map[tx][ty] == 1)  //撞上墙
        tx = Lorx[i-1],ty = Lory[i-1];
    Lorx[i] = tx,Lory[i] = ty;

    tx = Salx[i-1]+bak[st_Sal[(i-1)%st_Sal.length()]-48];
    ty = Saly[i-1]+bak[st_Sal[(i-1)%st_Sal.length()]-43];
    if ((tx<1)||(tx>n)||(ty<1)||(ty>m))
        tx = Salx[i-1],ty = Saly[i-1];
    else if (Map[tx][ty] == 1)
        tx = Salx[i-1],ty = Saly[i-1];
    Salx[i] = tx,Saly[i] = ty;
}

• 下面生成Sal的位置与Lor位置是一样的，就不写注释了。

• 然后主程序的最后一段：枚举Max_Deep，然后带入搜索：

  for (int i=1; i<=100; ++i)
  Search(i,0,Salx[0],Saly[0],0);  //i表示最大深度，第一个0表示现在小A走的步数，Salx[0]表示开始时的x坐标，Saly表示开始时的y坐标，最后一个0表示已经离开0秒

• 最后就是Search部分

void Search(int Max_Deep,int now,int nx,int ny,int Leave_Time)
{
    if (现在层数大于最大层数 或 离开时间大于s)
        return;
    if (到达魔王的位置)
    {
        printf("%d\n", now);
        exit(0);
    }
    now ++; //开始走
    for (int i=0; i<5; ++i)//五种方案：上下左右或者不动
    {
        int tx = nx+bak[i];
        int ty = ny+bak[i+5];
        int tk = Leave_Time;
        if ((tx<1)||(tx>n)||(ty<1)||(ty>m))
            continue;
        if (Map[tx][ty] == 1)
            continue;
        if (dist(tx,ty,Salx[now],Saly[now]) > r)
            tk++;
        else tk = 0;
        Search(Max_Deep,now,tx,ty,tk);
    }
}

• So，第五部分的代码实现就解决了，是不是觉得还比较简单，还有本人第二次在洛谷发布题解，不知道如何写才好，如果有没讲清楚的地方，尽管在评论中回复，我尽量做到有问必答。

第六部分 —— 后记

• 不知不觉就写了这么多了呢，希望各位给我一个赞，或是给予我您的宝贵的意见

• So，题解就到这了吧