每日一题-超级骑士-题解

超级骑士

题目描述

现在在一个无限大的平面上，给你一个超级骑士。
超级骑士有 $N$ 种走法，请问这个超级骑士能否到达平面上的所有点。
每种走法输入两个数字 $xx$ 和 $yy$ ，表示超级骑士可以从任意一点 $(x,y)$ 走到$(x+xx,y+yy)$。

输入格式

输入第一行为正整数 $T$ ，表示存在 $T$ 组测试数据。$(1≤T≤100)$
对于每组测试数据，第一行输入正整数N，表示有N种走法。$(1≤N≤100)$
接下来 $N$ 行，每行两个正整数 $xx$ 和 $yy$ 。$(-100≤xx,yy≤100)$

输出格式

对于每组测试数据，如果可以到达平面上所有点，输出Yes，否则输出No。

输入样例

2
3
1 0
0 1
-2 -1
5
3 4
-3 -6
2 -2
5 6
-1 4

输出样例

Yes
No

P1810 - [NewOJ Week 4] 超级骑士

思路

题目翻译一下就是，有 $T$ 组测试，每组测试数据给你 $N$ 个 $\vec{p} = (xx, yy)$ 向量，问你这 $N$ 个向量组成的向量组能不能和 $(1,0),(-1,0),(0,1),(0,-1)$ 等价，若能等价，则题目有解，反之无解。

那我们再翻译一下题目就是，能不能从一点出发，在 $m$ 步后到达它的上下左右四个点。这样我们便可以通过确定终点了。假设我们的起点为棋盘的中心，即 $(x,y) = (99,99)$ 则终点便是 $(100,99),(98,99),(99,100),(99,98)$ 。到此，开始搜索即可。

BFS 广度优先搜索

bool bfs(vector<pair<int, int> > &pos) {
    for (auto &i: visited)
        fill_n(i, 200, false);
    queue<pair<int, int> > q;
    q.emplace(x, y);
    visited[x][y] = true;
    while (not q.empty()) {
        int X = q.front().first, Y = q.front().second;
        q.pop();
        for (auto &i: pos) {
            int px = X + i.first, py = Y + i.second;
            if (px >= 0 and py >= 0 and px < 200 and py < 200
                and not visited[px][py]) {
                visited[px][py] = true;
                q.emplace(px, py);
            }
        }
        if (visited[x - 1][y] and visited[x + 1][y] and
            visited[x][y - 1] and visited[x][y + 1])
            return true;
    }
    return false;
}

DFS 深度优先搜索

在这题里，我写的深搜是这样的，在广搜跑出5424KB内存占用和214ms的用时时，这个深搜跑出了4612KB内存占用和1086ms的用时。[图见末尾AC截图]

bool dfs(vector<pair<int, int> > &pos, pair<int, int> now) {
    int &X = now.first, &Y = now.second;
    if (X == x and Y == y) {
        for (auto &i: visited)
            fill_n(i, 200, false);
    }
    visited[X][Y] = true;
    for (auto &i: pos) {
        int px = X + i.first, py = Y + i.second;
        if (px >= 0 and py >= 0 and px < 200 and py < 200
            and not visited[px][py])
            dfs(pos, {px, py});
    }
    if(X != x or Y != y)
        return false;
    return (visited[x - 1][y] and visited[x + 1][y] and
        visited[x][y - 1] and visited[x][y + 1]);
}

可以看出我写的这个深搜虽然内存占用更小，但是时间是广搜的五倍，优化空间很大，为此，我改成了迭代的写法。配合栈使用，效果拔群。[其实就是我的广搜代码的queue改成stack就好了，非常的神奇]它跑出了4964KB内存占用和214ms的用时

bool dfs(vector<pair<int, int> > &pos) {
    for (auto &i: visited)
        fill_n(i, 200, false);
    stack<pair<int, int> > sta;
    sta.emplace(x, y);
    visited[x][y] = true;
    while (not sta.empty()) {
        int X = sta.top().first, Y = sta.top().second;
        sta.pop();
        for (auto &i: pos) {
            int px = X + i.first, py = Y + i.second;
            if (px >= 0 and py >= 0 and px < 200 and py < 200
                and not visited[px][py]) {
                visited[px][py] = true;
                sta.emplace(px, py);
            }
        }
        if (visited[x - 1][y] and visited[x + 1][y] and
            visited[x][y - 1] and visited[x][y + 1])
            return true;
    }
    return false;
}

C++完整代码

#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>

using namespace std;
bool visited[200][200];
const int &x = 99, &y = 99;

bool bfs(vector<pair<int, int> > &pos) {
    for (auto &i: visited)
        fill_n(i, 200, false);
    queue<pair<int, int> > q;
    q.emplace(x, y);
    visited[x][y] = true;
    while (not q.empty()) {
        int X = q.front().first, Y = q.front().second;
        q.pop();
        for (auto &i: pos) {
            int px = X + i.first, py = Y + i.second;
            if (px >= 0 and py >= 0 and px < 200 and py < 200
                and not visited[px][py]) {
                visited[px][py] = true;
                q.emplace(px, py);
            }
        }
        if (visited[x - 1][y] and visited[x + 1][y] and
            visited[x][y - 1] and visited[x][y + 1])
            return true;
    }
    return false;
}

// 栈实现，深搜
bool dfs(vector<pair<int, int> > &pos) {
    for (auto &i: visited)
        fill_n(i, 200, false);
    stack<pair<int, int> > sta;
    sta.emplace(x, y);
    visited[x][y] = true;
    while (not sta.empty()) {
        int X = sta.top().first, Y = sta.top().second;
        sta.pop();
        for (auto &i: pos) {
            int px = X + i.first, py = Y + i.second;
            if (px >= 0 and py >= 0 and px < 200 and py < 200
                and not visited[px][py]) {
                visited[px][py] = true;
                sta.emplace(px, py);
            }
        }
        if (visited[x - 1][y] and visited[x + 1][y] and
            visited[x][y - 1] and visited[x][y + 1])
            return true;
    }
    return false;
}

// 标准深搜
bool dfs(vector<pair<int, int> > &pos, pair<int, int> now) {
    int &X = now.first, &Y = now.second;
    if (X == x and Y == y) {
        for (auto &i: visited)
            fill_n(i, 200, false);
    }
    visited[X][Y] = true;
    for (auto &i: pos) {
        int px = X + i.first, py = Y + i.second;
        if (px >= 0 and py >= 0 and px < 200 and py < 200
            and not visited[px][py])
            dfs(pos, {px, py});
    }
    if(X != x or Y != y)
        return false;
    return (visited[x - 1][y] and visited[x + 1][y] and
        visited[x][y - 1] and visited[x][y + 1]);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<pair<int, int> > vec(n);
        for (auto &i: vec) {
            int xx, yy;
            cin >> xx >> yy;
            i = {xx, yy};
        }
        cout << (dfs(vec) ? "Yes\n" : "No\n");
    }
    return 0;
}

AC截图