2024/1/29~2024/2/4

Wiki下象棋

题目链接:https://ac.nowcoder.com/acm/contest/74679/E

bfs搜两下就行了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


int fx[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
int fy[8] = {0, 0, -1, 1, -1, -1, 1, 1};

const int mod = 1000000007;
const int N = 200005;
const double eps = 1e-6;

int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] = {2, -2, 2, -2, 1, -1, 1, -1};
int bx[8] = {0, 0, 0, 0, 1, 1, -1, -1};
int by[8] = {1, -1, 1, -1, 0, 0, 0, 0};
int n, m;
bool vis[305][305], board[305][305];
int bfs1(int sx, int sy, int ex, int ey) {
  memcpy(vis, board, sizeof(vis));
  queue<pair<int, int> > q;
  q.push(make_pair(sx, sy));
  int cnt = 1, step = 0;
  vis[sx][sy] = true;
  while (!q.empty()) {
    int sum = 0;
    while (cnt--) {
      auto [x, y] = q.front();
      q.pop();
      if (x == ex && y == ey) return step;
      for (int i = 0; i < 8; ++i) {
        int fx = x + dx[i], fy = y + dy[i];
        if (fx < 1 || fy < 1 || fx > n || fy > m || vis[fx][fy]) continue;
        q.push(make_pair(fx, fy));
        vis[fx][fy] = true;
        ++sum;
      }
    }
    ++step;
    cnt = sum;
  }
  return -1;
}
int bfs2(int sx, int sy, int ex, int ey) {
  memcpy(vis, board, sizeof(vis));
  queue<pair<int, int> > q;
  q.push(make_pair(sx, sy));
  int cnt = 1, step = 0;
  vis[sx][sy] = true;
  while (!q.empty()) {
    int sum = 0;
    while (cnt--) {
      auto [x, y] = q.front();
      q.pop();
      if (x == ex && y == ey) return step;
      for (int i = 0; i < 8; ++i) {
        int fx = x + dx[i], fy = y + dy[i];
        if (fx < 1 || fy < 1 || fx > n || fy > m || vis[fx][fy] ||
            board[x + bx[i]][y + by[i]])
          continue;
        q.push(make_pair(fx, fy));
        vis[fx][fy] = true;
        ++sum;
      }
    }
    ++step;
    cnt = sum;
  }
  return -1;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T = 1;
  cin >> T;
  while (T--) {
    cin >> n >> m;
    int k, sx, sy, ex, ey;
    cin >> k >> sx >> sy >> ex >> ey;
    memset(board, false, sizeof(board));
    for (int i = 1; i <= k; i++) {
      int x, y;
      cin >> x >> y;
      board[x][y] = true;
    }
    cout << bfs1(sx, sy, ex, ey) << " " << bfs2(sx, sy, ex, ey) << endl;
  }
  return 0;
}