Advertisement
MathQ_

Untitled

Aug 20th, 2021
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.64 KB | None | 0 0
  1. const int n = 100, inf = 2e9;
  2. bool check(int i, int j) {
  3.     return 0 <= i && i <= 7 && 0 <= j && j <= 7;
  4. }
  5.  
  6. int f(int i, int j) {
  7.     return i * 10 + j;
  8. }
  9.  
  10. vector<vector<int>> g;
  11. int bfs(int st, int en) {
  12.     queue<int> q;
  13.     vector<int> dist(n, inf);
  14.     dist[st] = 0;
  15.     q.push(st);
  16.     while (!q.empty()) {
  17.         int v = q.front();
  18.         q.pop();
  19.         for (auto u : g[v]) {
  20.             if (dist[v] + 1 < dist[u]) {
  21.                 dist[u] = dist[v] + 1;
  22.                 q.push(u);
  23.             }
  24.         }
  25.     }
  26.     return (dist[en] == inf ? -1 : dist[en] - 1);
  27. }
  28.  
  29. int main() {
  30.     fast
  31.     // file_in
  32.  
  33.     map<char, vector<vector<pii>>> d;
  34.     // ферзь
  35.     d['Q'].resize(8);
  36.     for (int i = 1; i < 8; ++i) {
  37.         d['Q'][0].push_back({  i,  0});
  38.         d['Q'][1].push_back({  0,  i});
  39.         d['Q'][2].push_back({ -i,  0});
  40.         d['Q'][3].push_back({  0, -i});
  41.         d['Q'][4].push_back({  i,  i});
  42.         d['Q'][5].push_back({ -i,  i});
  43.         d['Q'][6].push_back({  i, -i});
  44.         d['Q'][7].push_back({ -i, -i});
  45.     }
  46.     // король
  47.     for (int i = -1; i <= 1; ++i) {
  48.         for (int j = -1; j <= 1; ++j) {
  49.             if (!i && !j) continue;
  50.             d['K'].push_back({{i, j}});
  51.         }
  52.     }
  53.     // конь
  54.     d['H'].push_back({{ -2,  1},
  55.                       { -2, -1},
  56.                       { -1,  2},
  57.                       { -1, -2},
  58.                       {  1,  2},
  59.                       {  1, -2},
  60.                       {  2,  1},
  61.                       {  2, -1}});
  62.  
  63.     // слон
  64.     d['E'].resize(4);
  65.     for (int i = 1; i < 8; ++i) {
  66.         d['E'][0].push_back({  i,  i});
  67.         d['E'][1].push_back({ -i,  i});
  68.         d['E'][2].push_back({  i, -i});
  69.         d['E'][3].push_back({ -i, -i});
  70.     }
  71.     // ладья
  72.     d['T'].resize(4);
  73.     for (int i = 1; i < 8; ++i) {
  74.         d['T'][0].push_back({  i,  0});
  75.         d['T'][1].push_back({  0,  i});
  76.         d['T'][2].push_back({ -i,  0});
  77.         d['T'][3].push_back({  0, -i});
  78.     }
  79.     // пешка
  80.     d['P'].push_back({{ 1, -1},
  81.                        {1, 1}});
  82.     g.resize(n);  
  83.     vector<vector<char>> mx(8, vector<char>(8));
  84.     cin >> mx;
  85.     int ki = -1, kj = -1;
  86.     for (auto &i : mx) for (auto &j : i) if (j == '#') j = '.';
  87.     for (int i = 0; i < 8; ++i) {
  88.         for (int j = 0; j < 8; ++j) {
  89.             for (auto dir : d[mx[i][j]]) {
  90.                 for (auto [di, dj] : dir) {
  91.                     if (check(i + di, j + dj)) {
  92.                         if (mx[i + di][j + dj] == '#' || mx[i + di][j + dj] == '.' || mx[i + di][j + dj] == 'h') {
  93.                             mx[i + di][j + dj] = '#';
  94.                         } else {
  95.                             break;
  96.                         }
  97.                     }
  98.                 }
  99.             }
  100.             if (mx[i][j] == 'K') ki = i, kj = j;
  101.         }
  102.     }
  103.     mx[ki][kj] = '.';
  104.     int st = -1, en = f(ki, kj);
  105.     for (int i = 0; i < 8; ++i) {
  106.         for (int j = 0; j < 8; ++j) {
  107.             if (mx[i][j] != '.' && mx[i][j] != 'h') continue;
  108.             if (mx[i][j] == 'h') st = f(i, j);
  109.             for (auto dir : d['H']) {
  110.                 for (auto [di, dj] : dir) {
  111.                     if (check(i + di, j + dj) && (mx[i + di][j + dj] == '.' || mx[i + di][j + dj] == 'h')) {
  112.                         g[f(i, j)].push_back(f(i + di, j + dj));
  113.                         g[f(i + di, j + dj)].push_back(f(i, j));
  114.                     }
  115.                 }
  116.             }
  117.         }
  118.     }
  119.     if (st == -1) {
  120.         cout << -1 << '\n';
  121.     } else {
  122.         cout << bfs(st, en) << '\n';
  123.     }
  124.    
  125.     return 0;
  126. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement