Програма для гри у шахи

На шаховій дошці розмірами M*N клітинок стоїть слон (фігура, що ходить по діагоналі). З'ясувати, чи може слон дійти до поля (х,у) Якщо може, то за яку найменшу кількість ходів; якщо кількість ходів більша за 1, то вказати, через які проміжні клітинки повинен пройти слон (якщо таких маршрутів кілька, вказати будь-який один з них). Поля шахової дошки кодуються парою натуральних чисел 1..M, 1..N, де перше число - номер горизонталі, а друге - номер вертикалі (1?M,N?1000). Технічні умови: Ви вводите з клавіатури через пропуск числа M, N, а далі координати початкового та кінцевого полів бажаного маршруту слона. Ви виводите на екран число К (мінімальна кількість ходів), а далі в К-1 рядках по 2 числа через пропуск - координати відвіданих полів. Якщо розв'язків немає, вивести 0.

Приклад:

Введення 10 10 1 1 1 7

Виведення 2 4 4

Рис.

2.Аналіз завдання

Розіб'ємо задачу на введення інформації, перевірку інформації за певних умов та виведення результату.

Для введення інформації використаємо діалог с користувачем. Поля шахової дошки кодуються парою натуральних чисел 1..M, 1..N, де перше число - номер горизонталі, а друге - номер вертикалі (1?M,N?1000). Просимо користувача ввести з клавіатури через пропуск числа M, N, а далі координати початкового та кінцевого полів бажаного маршруту слона.

Перевірка інформації полягає в двох аспектах. Перший, це відповідність умові. Другий, це пошук мінімального ходу за допомогою двох функцій : solve та show_result.

Після перевірки, програма виконується і виводиться мінімальна кількість ходів, або координата відвіданих полів.

комп'ютерний програма шахи

#include <stdio.h>

#include <math.h>

#include <iostream>

using namespace std;

int m, n, xb, yb, xe, ye;

// будемо додавати по кроку кожного разу, коли слон не може з поточної

//позиції перейти на кінцеву клітинку

int steps = 1; // кількість кроків

int intermediate_steps[999][2]; // координати середніх ходів

bool m_and_n_was_swapped = false;

// begin і end - координати початку руху та кінцевого пункту

bool begin_and_end_was_swapped = false;

int abs(int x)

{

return x < 0 ? -x : x;

}

void show_result()

{

// номер першої на вивід середньої клітинки, останньої та крок для

//циклу

int bg = 0, en = steps - 2, step = 1;

// номера першої та другої координати на вивід

int n1 = 0, n2 = 1;

// якщо початкова та кінцева клітинка помінялися місцями

// середні виводимо з останнього по перший

if (begin_and_end_was_swapped)

{

swap(bg, en);

step = -1;

}

if (m_and_n_was_swapped) swap (n1, n2);

cout << steps << endl;

for (int i = bg; i != en + step; i += step)

{

cout << intermediate_steps[i][n1];

cout << ' ' << intermediate_steps[i][n2] << endl;

}

}

void solve()

{

// якщо ширина дошки довше її висоти, поміняємо ці значення

// координати кожної точки, а у відповіді знову поміняємо х і у

// координати кожної точки (або просто виведемо у вигляді (у; х)

if (m > n)

{

swap(m, n);

swap(xb, yb);

swap(xe, ye);

m_and_n_was_swapped = true;

}

// якщо на отриманій дошці, в якій вже висота (за задумом)

// точно довше висоти, пункт призначення нижче початкової позиції

// слона, поміняемо ці точки((х1; у1) і (х2; у2)) місцями,

// а в відповіді виведемо точки в оберненому порядку

if (yb > ye)

{

swap(xb, xe);

swap(yb, ye);

begin_and_end_was_swapped = true;

}

// поки слон не може потрапити з 1 ходу з посаткової позиції

// на кінцеву, шукаємо наступну позицію

while (abs(xb - xe) != abs(yb - ye))

{

// перевіримо, чи можна за 2 ходи потрапити в кінцеву позицію

// для цього перевіримо чи можна з будь клітини, на яку можна

// перейти 1 ходом слона, потрапити одним ходом в кінцеву клітинку

bool can_reach_in_2_steps = false;

for (int x = 1; x <= m && !can_reach_in_2_steps; x++)

{

// цьому випадку клітинка, що перевіряється буде збігатися з

// кліткою, на якый знаходився слон, пропустимо її

int y = abs(xb - x) + yb;

if (abs(x - xe) == abs(y - ye))

{

// значить можна з клітини (xb; у1) потрапити на клітку (х2; у2)

// за два ходи, перенесемо слона (xb; у1) на клітинку (х; у),

// а в наступній перевірці цикла abs(xb - xe) != abs(yb - ye)

// поверне false, і пошук завершиться

can_reach_in_2_steps = true;

xb = x;

yb = y;

// додамо клітинку (х; у) в масив проміжних клітин

steps++;

// якщо кроків n (і n> 1), проміжних клітин n - 1,

// а номер останнього кроку n - 2 (через нумерації з нуля)

intermediate_steps[steps - 2][0] = x;

intermediate_steps[steps - 2][1] = y;

}

}

// якщо з двох ходів не дійти, просто піднімемося вище

if (!can_reach_in_2_steps)

{

if (xb - 1 > m - xb)

{

// якщо перший ряд далі, підемо вгору-вліво

// вгору підніметься на стільки клітин, на скільки і наліво

yb += xb - 1;

// а вліво до першого ряда

xb = 1;

}

else

{

// останній ряд далі, тому підемо вгору-вправо

// вгору підніметься на стільки клітин, на скільки і вправо

yb += m - xb;

// а вправо до першого ряда

xb = m;

}

// додамо клітку (xb; у1) в масив проміжних клітин

steps++;

// якщо кроків n (і n> 1), проміжних клітин n - 1,

// а номер останнього кроку n - 2 (через нумерації з нуля)

intermediate_steps[steps - 2][0] = xb;

intermediate_steps[steps - 2][1] = yb;

}

}

show_result();

}

bool check_input_data()

{

if (m < 1 || m > 1000) return false;

if (n < 1 || n > 1000) return false;

if (xb < 1 || xb > m) return false;

if (xe < 1 || xe > m) return false;

if (yb < 1 || yb > n) return false;

if (ye < 1 || ye > n) return false;

return true;

}

int main(void)

{

cin >> m >> n >> xb >> yb >> xe >> ye;

// перевірка ввідних даних на валідність

if (!check_input_data())

{

cout << "Invalid input data";

return 0;

}

// якщо початкова і кінцева клітинки різних кольорів

if ((xb + yb + xe + ye) % 2) cout << 0;

// якщо початкова та кінцева клітини збігаються

else if (xb == xe && yb == ye) cout << 0;

// якщо ширина або висота дошки дорівнює одиниці,

// то слон не може рухатися

else if (m == 1 || n == 1) cout << 0;

// інакше шукаємо кількість ходів і проміжні клітини

else solve();

return 0;

}

5.Контрольний приклад