fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int M, N, A, B;
  9.     if (!(cin >> M >> N >> A >> B)) return 0;
  10.  
  11.     int total = 2 * M * N;
  12.     if (A == B) {
  13.         cout << 0 << '\n';
  14.         return 0;
  15.     }
  16.  
  17.     vector<int> dist(total + 1, -1);
  18.     queue<int> q;
  19.     dist[A] = 0;
  20.     q.push(A);
  21.  
  22.     while (!q.empty()) {
  23.         int v = q.front(); q.pop();
  24.         int row = (v - 1) / (2 * M);
  25.         int rem = (v - 1) % (2 * M);
  26.         int col = rem / 2;
  27.         int tri = rem % 2; // 0 or 1
  28.  
  29.         // сосед в том же квадрате (парная плитка)
  30.         int base = row * (2 * M) + col * 2 + 1; // номер первой плитки в квадрате
  31.         int other = (v == base) ? base + 1 : base; // в квадрате всегда два: base и base+1
  32.         if (dist[other] == -1) {
  33.             dist[other] = dist[v] + 1;
  34.             if (other == B) { cout << dist[other] << '\n'; return 0; }
  35.             q.push(other);
  36.         }
  37.  
  38.         if (tri == 0) {
  39.             // tri==0 граничит сверху (row-1, same col) и слева (same row, col-1) с tri==1
  40.             if (row > 0) {
  41.                 int nb = (row - 1) * (2 * M) + col * 2 + 2; // tri==1 в квадрате выше
  42.                 if (dist[nb] == -1) {
  43.                     dist[nb] = dist[v] + 1;
  44.                     if (nb == B) { cout << dist[nb] << '\n'; return 0; }
  45.                     q.push(nb);
  46.                 }
  47.             }
  48.             if (col > 0) {
  49.                 int nb = row * (2 * M) + (col - 1) * 2 + 2; // tri==1 в квадрате слева
  50.                 if (dist[nb] == -1) {
  51.                     dist[nb] = dist[v] + 1;
  52.                     if (nb == B) { cout << dist[nb] << '\n'; return 0; }
  53.                     q.push(nb);
  54.                 }
  55.             }
  56.         } else { // tri == 1
  57.             // tri==1 граничит снизу (row+1, same col) и справа (same row, col+1) с tri==0
  58.             if (row + 1 < N) {
  59.                 int nb = (row + 1) * (2 * M) + col * 2 + 1; // tri==0 в квадрате ниже
  60.                 if (dist[nb] == -1) {
  61.                     dist[nb] = dist[v] + 1;
  62.                     if (nb == B) { cout << dist[nb] << '\n'; return 0; }
  63.                     q.push(nb);
  64.                 }
  65.             }
  66.             if (col + 1 < M) {
  67.                 int nb = row * (2 * M) + (col + 1) * 2 + 1; // tri==0 в квадрате справа
  68.                 if (dist[nb] == -1) {
  69.                     dist[nb] = dist[v] + 1;
  70.                     if (nb == B) { cout << dist[nb] << '\n'; return 0; }
  71.                     q.push(nb);
  72.                 }
  73.             }
  74.         }
  75.     }
  76.  
  77.     // если недостижимо (теоретически не должно быть при корректных входных данных)
  78.     cout << -1 << '\n';
  79.     return 0;
  80. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
5 4 39 15
stdout
copy 
8
https://ideone.com/xz4NXs
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!