пустая клетка else cout S[j % 2 + i % 2] S[j % 2 + i % 2];

cout endl;

cout

a b с d e f g h* endl endl;

Немного загадочное выражение j % 2 + i % 2 определяет символ (пробел или OxDB), соответствующий текущей клетке. Результат вызова Рг i nt Boar d () для начального расположения фигур показан на рис. 9.5.

abed

Рис 9.5. Вид шахматной доски на экране компьютера

Поскольку мы собираемся поставить мат чёрному королю на восьмой горизонтали, проверка на матовую ситуацию оказывается очень простой:

возвращает true, если чёрным поставлен мат

bool CheckMateO

return ВК.second ==8 чёрный король на восьмой горизонтали

&& WK.second ==6 белый король на шестой горизонтали

&& ВК.first == WK.first короли находятся в оппозиции

&& WR.second ==8; белая ладья на восьмой горизонтали

Теперь можно заняться самой важной функцией, выполняющей очередной ход белых. С точки зрения программирования в ней нет ничего сложного, но последовательность проверки различных условий и приоритетность принимаемых решений далеко не всегда очевидны.

Не скрою, первые версии этой функции нередко вели себя очень глупо и неоптимально. Быть может, изъянов не лишена и текущая реализация, но мне их обнаружить не удалось.

void WhiteMove()

if(ВК.first 1 WR.first) если король угрожает ладье слева { WR.first а; return; } переводим ладью на левый фланг if (ВК. first - 1 === WR. first) если король угрожает ладье справа { WR.first = h; return; ) переводим ладью на правый фланг

если чёрный король отошёл от ладьи ближе к краю доски if(ВК.second > WR.second +1) двигаем ладью ближе к королю { WR.second = ВК.second - 1; return; }

если чёрный король находится на вертикали а, а белый - на вертикали b делаем выжидательный ход ладьёй, вьшуждая следующим ходом чёрного короля стать в оппозицию if (ВК. first а && WK. first == Ь && ВК.second - WK.second 2)

{ WR.first-; return; } аналогично для правой вертикали

if(ВК.first == h && WK.first == g bb BK.second - WK.second == 2) { WR.first++; return; }

если короли находятся в оппозиции, делаем шах if(WK.first == ВК.first && BK.second - WK.second == 2) { WR.second++; return; )

pair<char, int> OldWK = WK;

если белый король находится по крайней мере на две клетки правее чёрного, двигаем белого короля влево if(WK.first - 1 > ВК.first) WK.first--;

else if(WK.first + 1 < BK.first) если левее - двигаем вправб WK.first++;

если белый король находится на слишком далёкой от чёрного горизонтали if(ВК.second - WK.second > 2)

WK.second++; двигаем белого короля вверх (то есть вперёд)

if (WK 1= OldWK) если белый король был сдвюгт, ход белых окончен return;

по возможности возвращаем белую ладью на ближайшую к ней крайнюю вертикаль if(WR.first i= а && WR.first <= d)

{ WR.first = a; return; } if(WR.first 1= h && WR.first >= e) { WR.first = h; return; }

если нет ходов получше,

просто сдвигаем ладью ближе к середине доски

ISaiatiausi

пока не поставили мат

считать ход чёрных с клавиатуры (ошибки не проверяются) ВК = pair<char, int>(move[0], atoi(move.substr(1).c str())); PrintBoaird () ; выполнить ход белыми WhiteMove(); PrintBoard();

return 0;

9.1.3. Чемпион по Minesweeper

Сложная стратегия для простой игры

Наверно, все знают эту замечательную маленькую игрупжу, входящую в состав ОС Windows (рис. 9.6). На прямоугольном поле расставлены мины (их

Ш1.!аилищ -:

Game Help

1 zrsW

.ISizii

l.SIZlt

количество зависит от сложности уровня). Цель игры - щёлкая мышью по клеткам, открыть все незаминированные области поля.

Если под очередной клеткой окажется мина, вам засчитьшается поражение. Если же клетка пуста, в ней отображается число мин, расположенных по соседству (у каждой клетки восемь соседних). Используя эту информацию, можно продвигаться по полю с меньшим риском. Например, единичка рядом с единственной закрытой клеткой однозначно сигнализирует: там мина!

Для удобства закрытые клетки можно метить флажками (если вы точно знаете, что туда лезть не следует, просто поставьте флажок на память).

При щелчке по клетке, не имеющей соседних мин, в стандартной реализации Minesweeper для Windows открывается вся безопасная область до первых ненулевых чисел включительно, а вместо нуля отображается пустая клетка.

Реализация игры - дело нехитрое. Будем считать это разминочной задачей. Интереснее запрограммировать алгоритм, достойно играющий в Minesweeper вместо человека.

Подсказка

Первый этап анализа игры очевиден. Пока все клетки закрыты, алгоритму ничего не остаётся, кроме как сделать один-два хода наудачу. Далее, если количество закрытых клеток, соседних с некоторой открытой, совпадает с числом, записанным в открытой клетке, можно сделать вывод: закрытые клетки содержат мины.

Если количество разведанных мин, примыкающих к открытой клетке, равно числу, записанному в ней, оставшиеся закрытые клетки можно смело открывать - мин там нет. Этот алгоритм играет, в лучшем случае, на уровне новичка.

Нередко игроку приходится делать ходы в условиях недостатка информации. При этом далеко не все опасные ходы опасны одинаково: попытаться открыть одну из восьми клеток, окружающих единицу, гораздо разумнее, чем одну из восьми клеток, окружаюп4Их четвёрку или пятёрку.

О стратегиях для игры в Minesweeper пишут целые статьи, и вставлять в книгу многочисленные страницы, посвященные анализу этой головоломки, мне кажется не совсем уместным. Лучше обратиться к первоисточникам. Для начала могу предложить две интересные ссылки:

Статья Sean Barret. Minesweeper: Advanced Tactics www.planet-minesweeper.com/advanced.php

Tniffle-Swine Keeper - программа-аналог Сапера (со встроенным решателем), исходный код которой доступен по адресу http: people.freenet.de/hskopp/swinekeeper.html

Рис. 9.6; Игра Minesweeper (Сапер)

if(WR.first <= d) WR.first++;

else

WR.first-;

Осталось написать простую функцию main (), отвечающую за разыгрывание эндшпиля между человеком и компьютером:

int main(int argc, char* argv[]) {

PrintBoardO ; while(!CheckMate()) {

string move; cin >> move;

ftlalaUausii

9.2.2. Архиватор монохромных изображений

9.2.1. Обработка сканированного изображения

Коррекция сканированной картинки: обрезка и поворот

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

Поскольку практически невозможно идеально ровно вложить лист бумаги в сканер, полученное изображение будет повёрнуто на некоторый (скорее всего, небольшой) угол. Это искажение несложно исправить автоматически, повернув картинку таким образом, чтобы границы текста сканированного документа были параллельны краям изображения.

Бумажные документы обычно имеют поля по краям, нередко довольно широкие. Поля же в отсканированном изображении приносят больше вреда, чем пользы. Избавиться от них при печати не удастся, указать свои собственные поля - тоже. Наилучшее решение состоит в обрезке сканированного документа, в результате чего на изображении остается только текст.

Итак, задача состоит в разработке программы, выполняющей поворот и обрезку сканированных изображений. На вход подаётся чёрно-белая картинка (двухцветная, без градаций серого), содержащая отсканированную страницу. На выход направляется она же, только повёрнутая и обрезанная.

Обратите внимание, что для выполнения каждого действия вам потребуется правильно определить границы текста на изображ(;нии. В принципе, предполагая чёрный текст на белом фоне, можно найти четыре крайних чёрных 1П1Кселя со всех сторон и считать их границами области. Однако при сканировании не исключено возникновение случайных черных пикселей за пределами текста. Лучше рассматривать изображение не на уровне отдельных пикселей, а, скажем, на уровне квадратов размером 3x3. Если такой квадрат содержит 3-4 чёрных точки, его уже можно считать краем области текста.

Подсказка

Если с обрезкой дела обстоят довольно просто, то функция поворота может вас несколько смутить. В действительности точки изображения ничем не отличаются от точек любой двумерной фигуры, и для операций с ними можно воспользоваться формулами, приведёнными в решении п. 2.1.3 ( Проволочная графика).

Алгоритм RLE

В предыдущей задаче нам пришлось столкнуться с чёрно-белыми изображениями, представляющими собой отсканированные страницы с текстом. Поскольку содержимое этих картинок весьма специфично (чёрный текст на белом фоне), можно попытаться разработать специализированный архиватор для их сжатия. Задача заключается в разработке алгоритма и программировании архиватора, умеющего выполнять сжатие и распаковку файлов, содержащих сканированный текст.

Формат изображения не играет роли. Если кому-то удобнее работать в BMP, пусть будет BMP, если PNG - тоже нет возражений. Единственное ограничение - отсутствие потерь качества при сжатии. Поэтому форматы вроде JPEG, предназначенные в первую очередь для фотографий, не годятся.

Подсказка

В качестве хорошей базы для экспериментов могу порекомендовать алгоритм RLE (Run-Length Encoding).

Он заменяет каждую последовательность из N одинаковых элементов числом N, благодаря чему достигается сжатие. В случае монохромных изображений эта методика работает особенно эффективно.

Пусть белый цвет (фон) кодируется нулём, а чёрный (тон) - единицей. Тогда последовательность:

00000000111000011111

будет заменена набором чисел:

8 3 4 5

Перед тем, как двигаться дальше, придётся сделать пару замечаний. Во-первых, мы считаем изображение потоком чисел О и 1, игнорируя его двумерную структуру (строки картинки хранятся друг за другом). Поэтому в сжатом файле необходимо сохранить информацию о ширине исходного изображения, чтобы распаковщик смог правильно восстановить оригинал.

Во-вторых, нет необходимости явно указывать, какой именно цвет соответствует набору из восьми, трёх, четырёх или пяти пикселей. За последовательностью белых точек всегда идёт последовательность чёрных и наоборот. Первый (верхний левый) пиксель картинки всегда считается белым. В противном случае первое число генерируемого набора будет равно нулю ( нуль белых точек ).

9.2. АНАЛИЗ И ОБРАБОТКА ИЗОБРАЖЕНИЙ