HDOJ 1175

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1175

题意简明，连连看，判断两个位置能不能消去。“不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。”——这句话真搞笑………令解题者少作一步处理，还是不错的（否则需要在棋盘外围加一圈0）。

很快写了个DFS的程序，提交上去，RE了，提示栈溢出。于是我习惯性地认为一定是DFS所用的递归函数导致栈溢出，于是改写，用STL的stack模板模拟递归。提交，继续栈溢出……

又不淡定了，难道stack中的元素也是在栈上的，改用vector？但是至多3000个节点怎么可能溢出……

忽然意识到问题所在了，我把1000*1000的int数组放在main函数里，一行声明代码就吃了4M栈空间，当然栈溢出了，只不过在我的OS X上正常运行……估计是OS X的栈空间较大。

激动地把数组移驾到全局，提交，TLE……

看同样用DFS的解题报告，原来是我没想到更牛逼的剪枝——譬如移动到A点时，已拐了2次——记录表明有个家伙在A点时才拐了1次，最终却没能到达终点，那么可以直接结束这条支线。

多么牛逼的剪枝啊！不过最后没有用这个方法，因为我不搜索了——依次判断直线到达，拐一次到达，拐两次到达。

直线到达最容易——依次判断直线上各点是否为0。

拐一次，可以得出两条轨迹，组成一个矩形……

拐两次，先求出两条平行线，然后作两平行线的垂线……

1w ms的限时，g++下62ms AC，看来不用搜索的效果还是不错的。

吐槽一下自己的代码，太长太面向对象，解题的代码没必要这样；但代码的事，我有点强迫症……

为了抽象不同方向上的操作，把坐标x, y表示为长度为2的数组，感觉还是有点用的。

吐槽一下自己以前在vim中没把tab设置成空格，造成博客上很多代码排版不齐，这次应该没问题。

这次加注释，中文注释……

//#define DEBUG

#include <cstdio>
#include <cassert>

#ifdef DEBUG
    #define ASSERT(A) assert(A)
    #define IS_LINE_LEGAL(LINE) ((LINE.dir_ == 0 || LINE.dir_ == 1)\
                                && LINE.low_ <= LINE.high_)
    #define DLog(A) printf(A)
#else
    #define ASSERT(A)
    #define IS_LINE_LEGAL(line)
    #define DLog(A)
#endif

const int HOR = 0;  //水平方向。
const int VER = 1;  //垂直方向。

inline int Ops(const int &dir)  //另一个方向。
{
    return ~dir & 1;
}

inline void Swap(int *const a, int *const b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

struct Location  //坐标类。
{
    int v_[2];  //v_[HOR]表示x，v_[VER]表示y_。

    Location() {}

    Location(const Location &loc)  //重定义拷贝构造函数，必须的。
    {
        v_[HOR] = loc.v_[HOR];
        v_[VER] = loc.v_[VER];
    }

    Location GetLocation(const int &dir, const int &dis)const  //返回在dir方向上，距本坐标dis的坐标。
    {
        Location loc;
        int ops_dir = Ops(dir);
        loc.v_[ops_dir] = v_[ops_dir];
        loc.v_[dir] = v_[dir] + dis;
        return loc;
    }

    bool IsEqual(const Location &loc)const
    {
        return v_[HOR] == loc.v_[HOR] && v_[VER] == loc.v_[VER];
    }
};

struct Line  //线段类。
{
    int dir_, low_, high_, v_;  //方向，两端点dir_方向坐标，线段反dir_方向坐标。

    void SetTwoEndpoints(const int &a, const int &b)  //设置两端点。
    {
        low_ = a;
        high_ = b;
        if (low_ > high_) Swap(&low_, &high_);
    }
};

int Min(const int &a, const int &b)
{
    return a < b ? a : b;
}

int Max(const int &a, const int &b)
{
    return a > b ? a : b;
}

struct Range
{
    int low_, high_;

    void SetRange(const Line &line_a, const Line &line_b)  //求两平行线的公共部分。
    {
        ASSERT(line_a.dir_ == line_b.dir_);
        ASSERT(IS_LINE_LEGAL(line_a));
        ASSERT(IS_LINE_LEGAL(line_b));

        low_ = Max(line_a.low_, line_b.low_);
        high_ = Min(line_a.high_, line_b.high_);
    }
};

struct Board  //连连看的主体部分，我称之为棋盘。
{
    int grids_[1001][1001];
    int width_, height_;

    int GetGrid(const Location &loc)const
    {
        ASSERT(IsLocationLegal(loc));

        return grids_[loc.v_[VER]][loc.v_[HOR]];
    }

    bool IsLocationLegal(const Location &loc)const  //判断坐标点存在。
    {
        return loc.v_[HOR] >= 1 && loc.v_[HOR] <= width_ &&
               loc.v_[VER] >= 1 && loc.v_[VER] <= height_;
    }

    Line GetLine(const Location &loc, const int &dir)const  //往两端延伸，直至不可通。
    {
        Line line;
        line.dir_ = dir;
        line.v_ = loc.v_[Ops(dir)];
        line.low_ = line.high_ = loc.v_[dir];

        for (int i=1; ; ++i) {
            Location temp = loc.GetLocation(dir, i);
            if (!IsLocationLegal(temp)) break;
            if (GetGrid(temp) != 0) break;
            line.high_ = temp.v_[dir];
        }
        for (int i=-1; ; --i) {
            Location temp = loc.GetLocation(dir, i);
            if (!IsLocationLegal(temp)) break;
            if (GetGrid(temp) != 0) break;
            line.low_ = temp.v_[dir];
        }

        return line;
    }

    bool IsLineOK(const Line &line)const  //线段可通。
    {
        ASSERT(IS_LINE_LEGAL(line));

        Location loc;
        const int &dir = line.dir_;
        int ops_dir = Ops(dir);
        loc.v_[ops_dir] = line.v_;

        for (int i=line.low_+1; i<line.high_; ++i) {
            loc.v_[dir] = i;
            if (GetGrid(loc) != 0) return false;
        }

        return true;
    }

    bool CanReachWithOutTurns(const Location &loc_a, const Location &loc_b)const
    {
        DLog("method CanReachWithOutTurns begin.\n");
        int dir = -1;
        if (loc_a.v_[HOR] == loc_b.v_[HOR]) {
            dir = VER;
        } else if (loc_a.v_[VER] == loc_b.v_[VER]) {
            dir = HOR;
        }
        if (dir == -1) return false;
        Line line;
        line.dir_ = dir;
        int ops_dir = Ops(dir);
        line.v_ = loc_a.v_[ops_dir];
        line.SetTwoEndpoints(loc_a.v_[dir], loc_b.v_[dir]);
        return IsLineOK(line);
    }

    bool CanReachWithOneTurnFromOneSide(const Location &loc_a,
                                        const Location &loc_b,
                                        const int &dir)const
    {
        Location loc;
        int ops_dir = Ops(dir);
        loc.v_[dir] = loc_a.v_[dir];
        loc.v_[ops_dir] = loc_b.v_[ops_dir];
        if (GetGrid(loc) != 0) return false;

        Line line_a;
        line_a.dir_ = ops_dir;
        line_a.v_ = loc.v_[dir];
        line_a.SetTwoEndpoints(loc.v_[ops_dir], loc_a.v_[ops_dir]);
        if (!IsLineOK(line_a)) return false;

        Line line_b;
        line_b.dir_ = dir;
        line_b.v_ = loc.v_[ops_dir];
        line_b.SetTwoEndpoints(loc.v_[dir], loc_b.v_[dir]);
        return IsLineOK(line_b);
    }

    bool CanReachWithOneTurn(const Location &loc_a, const Location &loc_b)const
    {
        return CanReachWithOneTurnFromOneSide(loc_a, loc_b, HOR) ||
               CanReachWithOneTurnFromOneSide(loc_a, loc_b, VER);
    }

    bool CanReachWithTwoTurnsFromOneSide(const Location loc_a,
                                         const Location loc_b,
                                         const int &dir)const
    {
        Line line_a = GetLine(loc_a, dir);
        Line line_b = GetLine(loc_b, dir);
        Range range;
        range.SetRange(line_a, line_b);
        int ops_dir = Ops(dir);
        
        for (int i=range.low_; i<=range.high_; ++i) {
            Line line;
            line.dir_ = ops_dir;
            line.v_ = i;
            line.SetTwoEndpoints(line_a.v_, line_b.v_);
            if (IsLineOK(line)) return true;
        }
        return false;
    }

    bool CanReachWithTwoTurns(const Location &loc_a, const Location &loc_b)const
    {
        return CanReachWithTwoTurnsFromOneSide(loc_a, loc_b, HOR) ||
               CanReachWithTwoTurnsFromOneSide(loc_a, loc_b, VER);
    }

    bool CanReach(const Location &loc_a, const Location &loc_b)const  //两待输入点是否可达。
    {
        DLog("method CanReach begin.\n");
        return CanReachWithOutTurns(loc_a, loc_b) ||
                CanReachWithOneTurn(loc_a, loc_b) ||
               CanReachWithTwoTurns(loc_a, loc_b);
    }

    bool IsProblemLegal(const Location &loc_a, const Location &loc_b)const  //两输入点的值是否相同且不为0。
    {
        if (loc_a.IsEqual(loc_b)) return false;
        int value_a = GetGrid(loc_a);
        return (value_a != 0 && value_a == GetGrid(loc_b));
    }

    bool CanEliminate(const Location &loc_a, const Location &loc_b)const  //两输入点是否可消去。
    {
        DLog("method CanEliminate begin.\n");
        return IsProblemLegal(loc_a, loc_b) && CanReach(loc_a, loc_b);
    }
} board;

int main()
{
    while (scanf("%d%d", &board.height_, &board.width_) != EOF &&
           board.height_ != 0) {
        
        for (int i=1; i<=board.height_; ++i) {
            for (int j=1; j<=board.width_; ++j) {
                scanf("%d", &board.grids_[i][j]);
            }
        }

        int count;
        scanf("%d", &count);
        while (count-- > 0) {
            Location a, b;
            scanf("%d%d%d%d", &a.v_[VER], &a.v_[HOR],
                              &b.v_[VER], &b.v_[HOR]);
            board.CanEliminate(a, b) ? printf("YES\n") : printf("NO\n");
        }
    }

    return 0;
}