Имя выходного файла: стандартный вывод Ограничение...

Question

Имя выходного файла: стандартный вывод
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 мегабайт
Перед своим вступлением в некоторую группу, Стэнли узнал, что для успешного принятия членами группы ему необходимо научиться играть в шахматы. Изучив правила, Стэнли понял, что в
этой древнейшей игре в действительности не хватает одной очень важной фигуры, которая ходит
как конь и слон одновременно.
Напомним, что если конь находится в клетке (r, c), то он может пойти во все такие клетки (x, y),
что |x − r| = 2 и |c − y| = 1, либо наоборот |x − r| = 1 и |c − y| = 2. При этом клетка (x, y) не должна
выходить за пределы поля.
Также напомним, если слон находится в клетке (r, c), то он может пойти во все такие клетки
(x, y), что |x − r| = |y − c|. При этом клетка (x, y) не должна выходить за пределы поля.
Вам дано шахматное поле размера n × n. Новая фигура находится в клетке (1, 1). Для каждой
клетки выведите минимальное количество ходов, необходимое, чтобы добраться до этой клетки,
либо -1, если добраться до клетки невозможно.
Формат входных данных
Единственная строка содержит целое число n (1 6 n 6 700) — размер шахматной доски.
Формат выходных данных
В n строках выведите по n целых чисел — минимальное количество ходов, необходимое, чтобы
добраться то текущей клетки, либо -1, если добраться до клетки невозможно.
Пример
стандартный ввод стандартный вывод
3 0 2 2
2 1 1
2 1 1
Замечание
Подзадачи:

5 баллов: n = 1
10 баллов: n 6 10
15 баллов: n 6 100
25 баллов: n 6 500
45 баллов: полные ограничения

#include <bits/stdc++.h>
#define int long long
using namespace std;

using i128 = __int128;
using ld = long double;
const int INF = 1e15;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;

int pw(int x, int st) {
if (st == 0) return 1;
if (st == 1) return x;

int ans = pw(x, st / 2);
ans = (ans * ans) % MOD;
if (st % 2) ans = (ans * x) % MOD;
return ans;
}

void solve() {
int n;
cin >> n;

if (n % 2 == 1) {
cout << 0;
return;
}
n /= 2;

vector< int > fac(N, 1);
for (int i = 2; i < N; i++) {
fac[i] = (fac[i - 1] * i) % MOD;
}

cout << (fac[n * 2] * pw((fac[n + 1] * fac[n]) % MOD, MOD - 2)) % MOD;
}

int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
srand(time(0));
int tests = 1;
//cin >> tests;
while (tests--) {
solve();
}

return 0;
}
реши задачу в моём стиле решение пиши в solve вне solve ничего не меняй bfs пиши

Answer 1

Да, здесь обычный BFS, но ходы слона нельзя каждый раз перебирать до края доски наивно — это может дать $O(n^3)$ . Однако при $n \le 700$ даже BFS с проходом по 4 диагоналям из каждой клетки потенциально слишком тяжёлый.

Можно заметить, что если клетка ещё не посещена, идём дальше по диагонали; если уже имеет расстояние меньше dist[v] + 1, дальше по этой диагонали можно не идти. Для такой задачи это стандартная оптимизация BFS по длинным ходам.

В твоём стиле, всё решение только внутри solve, вне него ничего не менял:

cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

using i128 = __int128;
using ld = long double;
const int INF = 1e15;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;

int pw(int x, int st) {
  if (st == 0) return 1;
  if (st == 1) return x;

  int ans = pw(x, st / 2);
  ans = (ans * ans) % MOD;
  if (st % 2) ans = (ans * x) % MOD;
  return ans;
}

void solve() {
  int n;
  cin >> n;

  vector< vector< int > > dist(n, vector< int >(n, -1));
  queue< pair< int, int > > q;

  dist[0][0] = 0;
  q.push({0, 0});

  int kx[8] = {2, 2, -2, -2, 1, 1, -1, -1};
  int ky[8] = {1, -1, 1, -1, 2, -2, 2, -2};

  int dx[4] = {1, 1, -1, -1};
  int dy[4] = {1, -1, 1, -1};

  while (!q.empty()) {
    auto [x, y] = q.front();
    q.pop();

    for (int i = 0; i < 8; i++) {
      int nx = x + kx[i];
      int ny = y + ky[i];

      if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;

      if (dist[nx][ny] == -1) {
        dist[nx][ny] = dist[x][y] + 1;
        q.push({nx, ny});
      }
    }

    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i];
      int ny = y + dy[i];

      while (nx >= 0 && nx < n && ny >= 0 && ny < n) {
        if (dist[nx][ny] == -1) {
          dist[nx][ny] = dist[x][y] + 1;
          q.push({nx, ny});
        } else if (dist[nx][ny] < dist[x][y] + 1) {
          break;
        }

        nx += dx[i];
        ny += dy[i];
      }
    }
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << dist[i][j] << ' ';
    }
    cout << '\n';
  }
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  srand(time(0));
  int tests = 1;
  //cin >> tests;
  while (tests--) {
    solve();
  }

  return 0;
}

Для примера n = 3 получится:

То есть совпадает с условием.

Имя выходного файла: стандартный вывод Ограничение...

Domanda

Pensiero

Risposta

Condividi questa Q&A