Luogu-P8854-超级马

题目 P8854 [POI2002] 超级马

题目描述

在一个大小为无限的棋盘上有一个超级马，它可以完成各种动作。

每一种动作包含两个整数，第一个数说明上下移动的数，第二个数说明左右移动的数，移动马来完成这个动作。（数字均为正数向右，负数向左）

请你对每一个输入的超级马进行确认，看它是否可以到达棋盘上的每一个地方。

输入格式

第一行中存在一个整数 $K$，表示数据组数。

对于每一组数据，第一行一个数 $N$，表示超级马能完成的动作个数。

接下来 $N$ 行，每一个行中包含两个整数 $P$ 和 $Q$，表示这个动作。

输出格式

输出 $K$ 行，判断超级马是否可以到达棋盘所有地方，可以输出 TAK，否则输出 NIE。

思路：bfs

等价题目

马能走到所有位置，当且仅当马能走到自己上下左右的相邻位置。

同时，因为存在负数坐标，所以应该考虑将坐标全部加上一个值 $k$，使得 $\forall (x,y),x+k \geq 0$ 且 $y+k \geq 0$。

注意

因为存在 $K$ 组数据，所以在每一组数据搜索前/后，应该把数组/全局变量设为初始值。

为什么不用dfs

• 本题只需要求出能/否，不需要求出类似方案数的量，因此在搜索到有效结果之后应立即返回。

• 我对于bfs()的定义为string bfs()，所以使用dfs可能造成返回值混乱。

AC Code

// template v5
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int inf = 0x7fffffff;

const int N = 210;
const int M = 110;

struct node {
    int x, y;
    bool vis;
} map_[N][N];
int dx[M];
int dy[M];
int n;

bool check() {
    return map_[99][100].vis && map_[101][100].vis && map_[100][99].vis && map_[100][101].vis;
}

bool valid(int x, int y) {
    return (x > 0 && x <= 200) && (y > 0 && y <= 200);
}

string bfs() {
    queue<node> q;
    q.push(map_[100][100]);
    map_[100][100].vis = true;
    while(q.size()) {
        node p = q.front();
        q.pop();
        for(int i = 0; i < n; i++) {
            int nx = p.x + dx[i],
                ny = p.y + dy[i];
            if(valid(nx, ny) && (!map_[nx][ny].vis)) {
                map_[nx][ny].vis = true;
                q.push(map_[nx][ny]);
                if(check()) return "TAK";
            }
        }
    }
    return "NIE";
}

int main() {
    int k;
    cin >> k;
    for(int i = 1; i <= 200; i++) {
        for(int j = 1; j <= 200; j++) {
            map_[i][j].x = i, map_[i][j].y = j;
        }
    }
    while(k-- > 0) {
        for(int i = 1; i <= 200; i++) {
            for(int j = 1; j <= 200; j++) {
                map_[i][j].vis = false;
            }
        }
        memset(dx, 0, sizeof dx);
        memset(dy, 0, sizeof dy);
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> dx[i] >> dy[i];
        }
        cout << bfs() << endl;
    }
    return 0;
}