#include <conio.h>
#include <dos.h>
#include <fstream.h>
#include <stdlib.h>
#include <string.h>
//**************************************************************************
// Программа для разгадывания японских кроссвордов.
// В качестве параметра задается имя файла, содержащего числа из кроссворда.
// Сначала записываются числа по вертикалям, сверху вниз. Числа, стоящие на
// одной строке, находятся на одной вертикали. Затем следует пустая строка,
// после которой идут числа по горизонталям слева направо. Количество строк
// и столбцов вычисляется автоматически.
//**************************************************************************
const del = 10; // Время задержки между анализом линий
// Класс, просматривающий все варианты для одной линии
class TVariant {
int length;
int number;
int HasModify;
char *variant;
char *positions;
char *currPos;
void MakeVariant (void);
int TestVariant (const char *line);
public:
int Build (char *line);
void NewVariant (const char *var);
int NextVariant (void);
const char *Variant (void)
{return variant;}
int len (void)
{return length;}
int num (void)
{return number;}
int modify (void)
{return HasModify;}
TVariant (int len, int num, const char *var)
{
HasModify = 0;
variant = new char [length = len];
positions = new char [number = num];
currPos = new char [num];
NewVariant (var);
}
~TVariant (void)
{
delete variant;
delete positions;
}
};
// Заполнить линию по начальным точкам закрашенных участков
void TVariant::MakeVariant (void)
{
setmem (variant, length, -1);
for (int i = 0; i < number; i++)
{
char *point = &variant [currPos [i]];
for (int j = 0; j < positions [i]; j++)
*point++ = 1;
}
}
// Проверить, допустим ли этот вариант
int TVariant::TestVariant (const char *line)
{
for (int i = 0; i < length; i++)
{
if (line [i] == -1 && variant [i] == 1 ||
line [i] == 1 && variant [i] == -1)
return 1;
}
return 0;
}
// Построить первый вариант размещения закрашенных клеток
void TVariant::NewVariant (const char *var)
{
memcpy (positions, var, number);
int n = 0;
for (int i = 0; i < number; i++)
{
currPos [i] = n;
n += positions [i] + 1;
}
if (n > length + 1)
{
cerr << "Error length\n";
exit (1);
}
MakeVariant ();
}
// Следующий вариант
int TVariant::NextVariant (void)
{
int num = number - 1;
do
{
currPos [num]++;
int n = currPos [num] + positions [num] + 1;
for (int i = num + 1; i < number; i++)
{
currPos [i] = n;
n += positions [i] + 1;
}
if (n <= length + 1)
{
MakeVariant ();
return 0;
}
}
while (--num >= 0);
return 1;
}
// Перебор всех возможных вариантов
int TVariant::Build (char *line)
{
char *test = new char [length];
memcpy (test, line, length);
int error = 1; // Флаг первого допустимого варианта
do
{
if (!TestVariant (test)) // Если вариант допустим
{
if (error) // Если первый вариант
{
error = 0;
memcpy (line, variant, length); // Запомнить его
}
else
for (int i = 0; i < length; i++) // Обозначить различные клетки как неопределенные
if (line [i] != variant [i])
line [i] = 0;
}
}
while (!NextVariant ());
HasModify = memcmp (test, line, length) != 0;
delete test;
return error;
}
//*******************************************************************
// Класс, описывающий поле (1 - закрашенная клетка, -1 - пустая,
// 0 - неопределенная)
class TArray {
int Width;
int Height;
int up;
int left;
int down;
int right;
int x;
int y;
char *array;
public:
int width (void)
{return Width;}
int height (void)
{return Height;}
char &pos (int x, int y)
{return array [x * Height + y];}
char get (int x, int y);
void GetVLine (char *line, int x);
void GetHLine (char *line, int x);
void PutVLine (const char *line, int x);
void PutHLine (const char *line, int x);
int test (void);
void window (int x1, int y1, int x2, int y2)
{up = x1; left = y1; right = x2; down = y2; x = 0; y = 0;}
void gotoxy (int x1, int y1)
{x = x1; y = y1;}
void draw (void);
TArray (int width, int height)
{
array = new char [width * height];
setmem (array, (Width = width) * (Height = height), 0);
::_wscroll = 0;
}
~TArray (void)
{delete array;}
};
// Счиитать отдельную ячейку поля
char TArray::get (int x, int y)
{
if (x < 0 || x >= Width || y < 0 || y >= Height)
return -1;
return array [x * Height + y];
}
// Считать вертикальную линию из поля
void TArray::GetVLine (char *line, int x)
{
char *point = array + (x * Height);
for (int i = 0; i < Height; i++, line++, point++)
*line = *point;
}
// Считать горизонтальную линию из поля
void TArray::GetHLine (char *line, int y)
{
char *point = array + y;
for (int i = 0; i < Width; i++, line++, point += Height)
*line = *point;
}
// Записать вертикальную линию в поле
void TArray::PutVLine (const char *line, int x)
{
char *point = array + (x * Height);
for (int i = 0; i < Height; i++, line++, point++)
*point = *line;
}
// Записать горизонтальную линию в поле
void TArray::PutHLine (const char *line, int y)
{
char *point = array + y;
for (int i = 0; i < Width; i++, line++, point += Height)
*point = *line;
}
// Проверяет, заполнено ли поле
int TArray::test (void)
{
char *point = array;
for (int len = Height * Width; len > 0; len--, point++)
if (*point == 0)
return 0;
return 1;
}
// Преобразует цвет символа и цвет фона в байт
inline int attr (int c, int b)
{
return (b << 4) + c;
}
// Возвращает номер цвета: для закрашенной клетки - 15 (белый),
// для пустой - 0 (черный), для неопределенной - 7 (серый)
inline int color (char byte)
{
if (byte == 0)
return 7;
if (byte == 1)
return 15;
return 0;
}
// Рисует поле на экране
void TArray::draw (void)
{
for (int i = 0; i < down; i++)
{
::gotoxy (left, up + i);
for (int j = 0; j < right; j++)
{
int k = i * 2;
char a = get (j + x, k + y );
char b = get (j + x, k + y + 1);
if (a == b)
{
textattr (attr (color (a), 0));
putch ('Ы'); // Символ для DOS
}
else if (a == 1)
{
textattr (attr (color (a), color (b)));
putch ('Я'); // Символ для DOS
}
else
{
textattr (attr (color (b), color (a)));
putch ('Ь'); // Символ для DOS
}
}
}
}
//*******************************************************************
char ver [100][10];
char hor [100][10];
int numVer, numHor;
// Улаляет пробелы в начале строки
void delSpace (char *str)
{
int len = strlen (str);
for (int i = 0; i < len && str [i] == ' '; i++);
for (int j = 0; i < len; str [j++] = str [i++]);
str [j] = 0;
for (i = strlen (str) - 1; i >= 0 && str [i] == ' '; i--);
str [i + 1] = 0;
}
// Преобразует строку в число, указатель перемещается на следующий символ
unsigned char num (char **str)
{
for (unsigned char n = 0; **str >= '0' && **str <= '9'; n = n * 10 + *((*str)++) - '0');
return n;
}
// Возвращает список чисел по нужной вертикали
int takeVer (char *line, int n)
{
for (int i = 0; i < 10 && ver [n][i] != 0; i++)
line [i] = ver [n][i];
return i;
}
// Возвращает список чисел по нужной горизонтали
int takeHor (char *line, int n)
{
for (int i = 0; i < 10 && hor [n][i] != 0; i++)
line [i] = hor [n][i];
return i;
}
int main (int argc, char *argv [])
{
if (argc != 2)
{
cerr << "Invalid parameter\n";
return 1;
}
ifstream in (argv [1]); // Открыть файл
char str [81];
for (int line = 0; !in.eof (); line++) // Считываются числа по вертикалям
{
in.getline (str, 80, '\n');
delSpace (str);
if (str [0] == 0)
break;
char *s = str;
for (int n = 0; *s != 0; n++)
{
ver [line][n] = num (&s);
delSpace (s);
}
}
if (in.eof ()) // Если конец файла - ошибка
{
cerr << "Invalid data in file\n";
return 1;
}
numVer = line; // Количество вертикалей
for (line = 0; !in.eof (); line++) // Считываются числа по горизонталям
{
in.getline (str, 80, '\n');
delSpace (str);
if (str [0] == 0)
break;
char *s = str;
for (int n = 0; *s != 0; n++)
{
hor [line][n] = num (&s);
delSpace (s);
}
}
numHor = line; // Количество горизонталей
in.close ();
TArray array (numVer, numHor); // Инициализация поля (все поля неопределенные)
array.window (1, 1, 80, 25);
array.draw (); // Нарисовать пустое поле
while (!array.test ()) // Пока поле не заполнено
{
char line [100], pos [10];
for (int i = 0; i < numVer; i++) // Проверка по вертикалям
{
array.GetVLine (line, i);
int n = takeVer (pos, i);
TVariant variant (numHor, n, pos);
variant.Build (line);
array.PutVLine (line, i);
delay (del);
array.draw ();
}
for (i = 0; i < numHor; i++) // Проверка по горизонталям
{
array.GetHLine (line, i);
int n = takeHor (pos, i);
TVariant variant (numVer, n, pos);
variant.Build (line);
array.PutHLine (line, i);
delay (del);
array.draw ();
}
}
return 0;
}
