Snake Problem

题目

在一个平面上，有n+m条蛇，其中n条蛇沿水平方向（y轴方向）移动，m条蛇沿竖直方向（x轴方向）移动。

现给出这些蛇头和尾所在的坐标点，求出这n+m条蛇在此时共有多少个交点。在同一个方向移动的蛇不会有交点。

如图所示，n = 5, m = 4，这些蛇一共有5个交点。

Alt text

分析

对于此题，最简单直接的方法就是枚举蛇两两之间的关系，这种算法的时间复杂度为O(n^2)。

当然，我们不能满足于这种暴力的解法。那么，有没有更优美的方法呢？

Alt text

对于这一条在y轴方向上的（红）蛇来说，它与x轴方向上的（黑）蛇共有三个交点。那么，也就意味着，问题的关键在于，我们如何快速确定某一条红蛇（或黑蛇）与其它蛇一共有多少个交点。

我们可以做出如下假设，我们知道当x = k时，所有在平面上的蛇的位置。根据这个假设，我们可以使用区间求和的算法来确定竖直位置上的蛇会有多少个焦点。

假设我们从x = 0到x = MAX_X方向进行扫描，每条蛇在扫描时，都有且只有两种状态：

  1. 扫描线第一次经过蛇的某端点
  2. 扫描线第二次经过蛇的另一个端点（废话！）

这两个状态分别意味着某一条黑蛇在x = k时是否存在。我们维护一个数组，数组中第u个元素代表y = u的黑蛇是否在x = k时存在。

这个时候，当我们查询一条x = [v, w]位置的红蛇共有多少个交点时，只需要计算数组中[v ... w]元素的和。而使用树状数组(Binary Indexed Tree, BIT)，每次这样的查询只需要O(logN)时间。

所以，总的时间复杂度为O(N * logN)，比O(N^2)的算法优化了很多。

代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

const int SIZE = 1024;

inline int lowbit(int x) { return x & (-x); }

struct BITree {
    int _tree[SIZE];
    void init() {
        memset(_tree, 0, sizeof(_tree));
    }
    void add(int x, int p) {
        while (p < SIZE) {
            _tree[p] += x;
            p += lowbit(p);
        }
    }
    int sum(int p) {
        int res = 0;
        while (p > 0) {
            res += _tree[p];
            p -= lowbit(p);
        }
        return res;
    }
    int sum(int a, int b) {
        return sum(b) - sum(a - 1);
    }
};

struct Point { int x, y; };
struct Snake { Point start, end; };

class Solution { // manual tested
public:
    int count_intersection(const vector<Snake>& xsnakes,
            const vector<Snake>& ysnakes) {
        int ans = 0;
        _tree.init();
        vector<Mark> vec;
        for (auto s: xsnakes) {
            vec.push_back(Mark({s.start.x, 1, s.start.y}));
            vec.push_back(Mark({s.end.x,  -1, s.end.y}));
        }
        int p = 0;
        for (auto s: ysnakes) {
            vec.push_back(Mark({s.start.x, 0, p++}));
        }
        sort(vec.begin(), vec.end());
        for (auto mark: vec) {
            if (mark.type == 1) {
                _tree.add(1, mark.val);
            } else if (mark.type == -1) {
                _tree.add(-1, mark.val);
            } else {
                p = mark.val;
                int a = ysnakes[p].start.y;
                int b = ysnakes[p].end.y;
                ans += _tree.sum(a, b);
            }
        }
        return ans;
    }
private:
    struct Mark {
        int pos, type, val;
        friend bool operator < (const Mark& a, const Mark& b) {
            return a.pos < b.pos;
        }
    };
    BITree _tree;
};

int main() {
    vector<Snake> xsnakes({
        Snake({ Point({1, 2}), Point({5, 2}) })
    });
    vector<Snake> ysnakes({
        Snake({ Point({2, 1}), Point({2, 3}) }),
        Snake({ Point({3, 1}), Point({3, 3}) })
    });
    Solution S;
    print(S.count_intersection(xsnakes, ysnakes));
    return 0;
}

题目来源

《算法引论》

扩展题目

POJ-2482 Stars in Your Window

Comments

comments powered by Disqus