1197. Одинокий конь

На шахматной доске стоит конь. Необходимо определить количество ходов, доступных ему из заданного поля.

Вход. Первая строка содержит количество тестов n (1 £ n £ 100). Каждая следующая строка задает поле, на котором находится конь, в шахматной нотации. Первым символом является буква от ‘a’ до ‘h’, вторым – цифра от 1 до 8.

Выход. Для каждого теста вывести количество полей, куда может пойти конь из заданного.

Пример входа

3

a1

d4

g6

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

2

8

6

РЕШЕНИЕ

перебор

Анализ алгоритма

Из точки шахматной доски конь может сделать 8 ходов. Но некоторые хода могут вести в клетки, находящиеся за пределами шахматной доски. Опишем функцию cango(x, y), которая возвращает 1, если поле (x, y) находится на шахматной доске и 0 иначе. Для каждого теста рассматриваем поля, куда может пойти конь, и подсчитываем такое их количество, которое не выходит за границы шахматной доски.

Реализация алгоритма

Все возможные ходы коня опишем в массивах xx и yy, где (xx[i], yy[i]), 1 £ i £ 8, является смещением хода коня.

int xx[8] = {1,1,-1,-1,2,2,-2,-2};

int yy[8] = {2,-2,2,-2,1,-1,1,-1};

Функция cango(x, y) возвращает 1, если поле (x, y) находится на шахматной доске и 0 если за ее пределами.

int cango(int x, int y)

{

if ((x < 1) || (x > 8) || (y < 1) || (y > 8)) return 0;

return 1;

}

Основной цикл программы. Читаем количество тестов n.

scanf("%d\n",&n);

while(n--)

{

Читаем данные текущего теста – координаты коня в целочисленные переменные (x, y).

scanf("%c%d\n",&x,&y); x -= 'a' - 1;

Рассматриваем все возможные 8 ходов коня. Если очередной ход совершается на клетку доски (а не за ее пределы), то увеличиваем значение res на 1. После выполнения цикла выводим res – количество допустимых ходов коня.

res = 0;

for(i=0;i<8;i++)

if (cango(x+xx[i],y+yy[i])) res++;

printf("%d\n",res);

}