Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const int n = 100, inf = 2e9;
- bool check(int i, int j) {
- return 0 <= i && i <= 7 && 0 <= j && j <= 7;
- }
- int f(int i, int j) {
- return i * 10 + j;
- }
- vector<vector<int>> g;
- int bfs(int st, int en) {
- queue<int> q;
- vector<int> dist(n, inf);
- dist[st] = 0;
- q.push(st);
- while (!q.empty()) {
- int v = q.front();
- q.pop();
- for (auto u : g[v]) {
- if (dist[v] + 1 < dist[u]) {
- dist[u] = dist[v] + 1;
- q.push(u);
- }
- }
- }
- return (dist[en] == inf ? -1 : dist[en] - 1);
- }
- int main() {
- fast
- // file_in
- map<char, vector<vector<pii>>> d;
- // ферзь
- d['Q'].resize(8);
- for (int i = 1; i < 8; ++i) {
- d['Q'][0].push_back({ i, 0});
- d['Q'][1].push_back({ 0, i});
- d['Q'][2].push_back({ -i, 0});
- d['Q'][3].push_back({ 0, -i});
- d['Q'][4].push_back({ i, i});
- d['Q'][5].push_back({ -i, i});
- d['Q'][6].push_back({ i, -i});
- d['Q'][7].push_back({ -i, -i});
- }
- // король
- for (int i = -1; i <= 1; ++i) {
- for (int j = -1; j <= 1; ++j) {
- if (!i && !j) continue;
- d['K'].push_back({{i, j}});
- }
- }
- // конь
- d['H'].push_back({{ -2, 1},
- { -2, -1},
- { -1, 2},
- { -1, -2},
- { 1, 2},
- { 1, -2},
- { 2, 1},
- { 2, -1}});
- // слон
- d['E'].resize(4);
- for (int i = 1; i < 8; ++i) {
- d['E'][0].push_back({ i, i});
- d['E'][1].push_back({ -i, i});
- d['E'][2].push_back({ i, -i});
- d['E'][3].push_back({ -i, -i});
- }
- // ладья
- d['T'].resize(4);
- for (int i = 1; i < 8; ++i) {
- d['T'][0].push_back({ i, 0});
- d['T'][1].push_back({ 0, i});
- d['T'][2].push_back({ -i, 0});
- d['T'][3].push_back({ 0, -i});
- }
- // пешка
- d['P'].push_back({{ 1, -1},
- {1, 1}});
- g.resize(n);
- vector<vector<char>> mx(8, vector<char>(8));
- cin >> mx;
- int ki = -1, kj = -1;
- for (auto &i : mx) for (auto &j : i) if (j == '#') j = '.';
- for (int i = 0; i < 8; ++i) {
- for (int j = 0; j < 8; ++j) {
- for (auto dir : d[mx[i][j]]) {
- for (auto [di, dj] : dir) {
- if (check(i + di, j + dj)) {
- if (mx[i + di][j + dj] == '#' || mx[i + di][j + dj] == '.' || mx[i + di][j + dj] == 'h') {
- mx[i + di][j + dj] = '#';
- } else {
- break;
- }
- }
- }
- }
- if (mx[i][j] == 'K') ki = i, kj = j;
- }
- }
- mx[ki][kj] = '.';
- int st = -1, en = f(ki, kj);
- for (int i = 0; i < 8; ++i) {
- for (int j = 0; j < 8; ++j) {
- if (mx[i][j] != '.' && mx[i][j] != 'h') continue;
- if (mx[i][j] == 'h') st = f(i, j);
- for (auto dir : d['H']) {
- for (auto [di, dj] : dir) {
- if (check(i + di, j + dj) && (mx[i + di][j + dj] == '.' || mx[i + di][j + dj] == 'h')) {
- g[f(i, j)].push_back(f(i + di, j + dj));
- g[f(i + di, j + dj)].push_back(f(i, j));
- }
- }
- }
- }
- }
- if (st == -1) {
- cout << -1 << '\n';
- } else {
- cout << bfs(st, en) << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement