MTK编程挑战赛《算术迷宫》

tags: soj 联发科技杯 编程挑战赛

2017 “联发科技杯”编程挑战赛决赛 第3题 《算术迷宫》

题目描述

你一觉醒来,发现和一群人身处一个迷宫之中。每个人的手上都印着一个数字。 经过一段时间的摸索,大家知道了迷宫的结构,如下:

      +-----------+      +-----------+
      |    +7     |      |    *3     |
+-----+   +---+   +------+   +---+   +------+
   X      |   |              |   |      Y
+-----+   +---+   +------+   +---+   +------+
      |    /2     |      |    -5     |
      +-----------+      +-----------+

大家还发现迷宫有一些规律:

  1. 迷宫中几处路口写着算术式,经过这些路口时,手上的数字会按算术发生变化。
  2. 如果手上的数字为奇数,则无法通过“/2”这条路。
  3. 在迷宫中可以朝任何方向走,但不能回头(不能连续通过同一个算术点)。
  4. 迷宫的出口大门上写着一个数字,当你来到出口同时手上的数字跟大门上的一致时,门才能打开。

现在你和所有其它人一样被放在迷宫的起点。希望你能找到一种方法,让大家在国庆节前逃出来。 全靠你了,少年!

输入说明

在程序当前目录下存在execute.stdin文件,程序从execute.stdin中取得输入数据。execute.stdin为单行文件,里面存放着两个正整数X和Y,用空格隔开,分别表示起点和出口的数字。

输出说明

请单行输出解决方案的算术表达式。

样例

execute.stdin内容:1 84
预期输出为:1+7/2+7*3-5*3=84

* 迷宫规则的第3条原文为,“在迷宫中可以转圈,但不能回头。”现场发现不太好理解,这里修正了一下。


分析

首先习惯性的先用数学手法来分析。但随便走一走,就会迷茫了。应该看出,这个迷宫找不出数学规律。然后思考,怎么借助计算机的能力来解决。

迷宫中有三个位置:起点、中间点、终点。每个点上都可能有多个前进方向。如果把行走的方式像下面那样画下来:

                      +--(*3)-->> P2 --+--(-5)-->> P1 --??
                      |
                      +--(-5)-->> P2 --+--(*3)-->> P1 --??
                      |
P0 --+--(+7)-->> P1 --+--(/2)-->> P0 --+--(+7)-->> P1 --??
     |
     +--(/2)-->> P1 --+--(+7)-->> P0 --+--(/2)-->> P1 --??
                      |
                      +--(*3)-->> P2 --+--(-5)-->> P1 --??
                      |
                      +--(-5)-->> P2 --+--(*3)-->> P1 --??
大家熟悉的东西出现了:这正好是一棵树。而另外两个限制条件则要求我们剪掉树的某些分支:

  1. 不能回头。例如,刚刚走过(+7)这条路,就不能立即回头再走(+7)。
  2. 当前数字为奇数时,不能走(/2)这条路。

于是这个问题就可以转化成:带着数字X从树根P0出发,去寻找类型为P2且数字变为Y的节点。我们经过的路径就是迷宫的出路。

这道题其实就是做树的搜索了。

DFS or BFS?

在树上搜索节点有两种典型的算法:深度优先搜索(DFS)和广度优先搜索(BFS)。用哪一种比较好呢?

这个迷宫树是无穷深且无规律可循,我们无法估算出最终路径的长度范围。如果用DFS,程序可能会陷入某一分支不能出来,这种情形CPU和内存都无法接受。而BFS则一层一层向下找,可以确保在有限的深度找到最短的路径。

所以BFS是更好的选择。

Recursive or Non-Recursive?

运用递归在很多场合下可以简化代码逻辑。但是否应该使用递归,需要考量递归深度对栈空间的压力。跟前面DFS的考察一样,这棵树的任一分枝都可能是深不可测的,所以原则上这道题并不适合递归。

当然,如果你的代码能恰当的实现“尾递归”,就不用担心栈空间问题。

参考解法

/*********************************************************************
 *
 * Hua Shao <nossiac@163.com>
 *
 * MediaTek 2017 Coding Contest, Final, "Arithmetic Maze".
 *
 *********************************************************************/

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

class WayPoint
{
public:
    int pos; // current position
    int i; // current number
    vector<int> path; // path so far
    WayPoint(int pos, int i, vector<int> path)
    {
        this->pos = pos;
        this->i = i;
        this->path = path;
    }
    WayPoint(int pos, int i)
    {
        this->pos = pos;
        this->i = i;
        this->path.push_back(0); // start point
    }
    static int X; // origin number
    static int Y; // target number
    static int n; // number of nodes been searched
};

int WayPoint::X = 0;
int WayPoint::Y = 0;
int WayPoint::n = 0;

bool OK(WayPoint * now)
{
    if (now->i == now->Y && now->pos == 2)
    {
        vector<int>::const_iterator i;
        for (i=now->path.begin(); i!=now->path.end(); ++i)
        {
            switch (*i)
            {
                case 0:
                    cout<<now->X;
                    break;
                case 2:
                    cout<<"/2";
                    break;
                case 7:
                    cout<<"+7";
                    break;
                case 3:
                    cout<<"*3";
                    break;
                case 5:
                    cout<<"-5";
                    break;
                default:
                    cout<<"??"<<endl;
                    break;
            }
        }
        cout<<"="<<now->Y<<endl;
        return true;
    }
    return false;
}



void BFS(int X, int Y)
{
    deque<WayPoint*> togo;
    WayPoint * now = new WayPoint(0, X);
    WayPoint * next = NULL;
    now->X = X;
    now->Y = Y;
    while (now)
    {
        if (now->pos == 0)
        {
            if (now->path.back() != 7)
            {
                next = new WayPoint(now->pos, now->i, now->path);
                next->i += 7;
                next->path.push_back(7);
                next->pos = 1;
                togo.push_back(next);
            }

            if (now->i%2 == 0 && now->path.back() != 2)
            {
                next = new WayPoint(now->pos, now->i, now->path);
                next->i /= 2;
                next->path.push_back(2);
                next->pos = 1;
                togo.push_back(next);
            }
        }
        else if (now->pos == 1)
        {
            if (now->path.back() != 7)
            {
                next = new WayPoint(now->pos, now->i, now->path);
                next->i += 7;
                next->path.push_back(7);
                next->pos = 0;
                togo.push_back(next);
            }

            if (now->i%2 == 0 && now->path.back() != 2)
            {
                next = new WayPoint(now->pos, now->i, now->path);
                next->i /= 2;
                next->path.push_back(2);
                next->pos = 0;
                togo.push_back(next);
            }

            if (now->path.back() != 3)
            {
                next = new WayPoint(now->pos, now->i, now->path);
                next->i *= 3;
                next->path.push_back(3);
                next->pos = 2;
                if (OK(next)) break;
                togo.push_back(next);
            }

            if (now->path.back() != 5)
            {
                next = new WayPoint(now->pos, now->i, now->path);
                next->i -= 5;
                next->path.push_back(5);
                next->pos = 2;
                // cout<<"-5"<<endl;
                if (OK(next)) break;
                togo.push_back(next);
            }
        }
        else if (now->pos == 2)
        {
            if (now->path.back() != 3)
            {
                next = new WayPoint(now->pos, now->i, now->path);
                next->i *= 3;
                next->path.push_back(3);
                next->pos = 1;
                togo.push_back(next);
            }

            if (now->path.back() != 5 && now->i >= 5)
            {
                next = new WayPoint(now->pos, now->i, now->path);
                next->i -= 5;
                next->path.push_back(5);
                next->pos = 1;
                togo.push_back(next);
            }
        }

        now->n++;
        // discard current node
        delete(now);
        // try next node
        now = togo.front();
        togo.pop_front();
    }
}


int main(int argc, char const *argv[])
{
    BFS(1, 84); 
    BFS(2011, 2012);    
    return 0;
}

代码简述

首先我们定义了一个WayPoint类,用来表示树上的节点。这个节点上保存了三个信息:当前位置,当前数字,当前已经走过的路径。

定义了一个deque<WayPoint*>,用来保存待BFS探索的节点。遇到一个节点,我们去探索它的子节点(也即可能的行走方向)。如果子节点不符合要求,则将它加入deque里。下次取出来时,我们会再从该子节点向下探索。

OK()函数用于判断当前节点是否符合要求。因为只有P2类型的节点才可能是出口,所以我们只在目标为P2的方向上做了判断。

优化?

示例解法将当前走过的路径都保存在WayPoint::path里,输出解法的时候比较方便。为了节省一些内存,我们将搜索过但不符合要求的节点都delete掉了。

另一种方案是只在WayPoint里保存一个指向父节点的指针,单个节点内存开销比vector要少。不过不能再delete任何节点了。因为在输出解法时,我们需要从当前节点一路逆推到根节点。

在一般规模下,两种方式各有千秋,差别不大,都可取。


后记

这道题是决赛中最难的两题之一。现场没有人做出来,实际上提交解法的都没有几个。

原因一是时间不够用了。大部分参赛队都是先易后难的策略,等其它题解完了,总时间也花得差不多了。剩下的时间不够解决这道题了。另外有一些队选择的是分头进攻,有人专门来攻这道题,但可惜的是,离成功就差一点点。

原因二是题目描述中的“不能回头”的说法有些模糊、抽象,有几个参赛队员误解了回头的意思,认为是不能从第二个回字型回到第一个回字型,所以一直没有找到正确的思路。题目括号中的说明也是现场临时补充上去的。

赛后我也仔细看了几位选手提交的解法,发现个别已经很接近成功了:有一位选手失败在搜索时用了DFS,第一组测试数据过关了,但第二组测试数据就沦陷在某个分支出不来了,30秒都没有搜出答案。另一位选手思路是正确的,只是代码编写上有一些失误。可能是BFS用得不太熟练,挺可惜的。