Матч 334, Путь коня (KnightTour)

Дивизион 2, Уровень 2

Допустимым путем шахматного коня на доске 6*6 назовем такую последовательность ходов, при которой посещаются все поля доски, а из последней клетки пути конь может попасть в первую (путь является замкнутым). Например, один из возможных таких путей, начинающийся в “A1” и заканчивающийся в “C2”, изображен на рисунке:

Путь коня задается в массиве cells, каждый элемент которого является строкой вида “<буква><цифра>”. Каждая такая строка описывает координату хода коня на доске. По заданному пути необходимо определить, является ли он допустимым.

Класс: KnightTour

Метод: string checkTour(vector<string> cells)

Ограничения: cells содержит в точности 36 строк в формате “<буква><цифра>”, где ‘A’ £ <буква> £ ‘F’, 1 £ <цифра> £ 6.

Вход. Массив строк cells, описывающий путь коня.

Выход. Если путь допустимый, то вернуть “Valid”, иначе “Invalid”.

Пример входа

cells

{"A1", "B3", "A5", "C6", "E5", "F3",
"D2", "F1", "E3", "F5", "D4", "B5",
"A3", "B1", "C3", "A2", "C1", "E2",
"F4", "E6", "C5", "A6", "B4", "D5",
"F6", "E4", "D6", "C4", "B6", "A4",

"B2", "D1", "F2", "D3", "E1", "C2"}

{"A1", "C2", "E3", "F5", "D4", "B3",
"A1", "C2", "E3", "F5", "D4", "B3",
"A1", "C2", "E3", "F5", "D4", "B3",
"A1", "C2", "E3", "F5", "D4", "B3",
"A1", "C2", "E3", "F5", "D4", "B3",

"A1", "C2", "E3", "F5", "D4", "B3"}

{"D4", "F5", "D6", "B5", "A3", "B1",
"D2", "F1", "E3", "D1", "F2", "E4",
"F6", "D5", "B6", "A4", "B2", "C4",
"A5", "C6", "E5", "F3", "E1", "C2",
"A1", "B3", "C5", "E6", "F4", "E2",

"C3", "A2", "C1", "D3", "B4", "A6"}

Пример выхода

“Valid”

“Invalid”

“Invalid”

РЕШЕНИЕ

моделирование

Заведем массив vis[6][6], в котором будем отмечать ходы коня: vis[i][j] = 1, если в клетке (i, j) уже побывал конь и vis[i][j] = 0 иначе. На вход функции cango подаются координаты двух клеток a и b. Она возвращает истину, если конь может пройти из клетки a в клетку b. Последнее возможно, если клетка b еще не была пройдена, а клетки a и b находятся друг от друга на расстоянии одного хода коня.

Имея массив cells, моделируем движение коня. Если какой-нибудь ход невозможен, устанавливаем переменную flag в 1 и выходим из цикла. В зависимости от значения переменной flag возвращаем результат.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <cmath>

using namespace std;

int vis[6][6];

int cango(string a, string b)

{

int v1 = a[0] - 'A';

int h1 = a[1] - '0';

int v2 = b[0] - 'A';

int h2 = b[1] - '0';

if (vis[v1][h1]) return 0;

vis[v1][h1] = 1;

int dx = abs(v1 - v2);

int dy = abs(h1 - h2);

return (((dx == 1) && (dy == 2)) || ((dx == 2) || (dy == 1)));

}

class KnightTour

{

public:

string checkTour(vector<string> cells)

{

int i, flag;

memset(vis,0,sizeof(vis));

cells.push_back(cells[0]);

for(flag = i = 0; i < cells.size() - 1; i++)

if(!cango(cells[i],cells[i+1])) {flag = 1; break;}

return (flag) ? "Invalid" : "Valid";

}

};