Основы программирования

Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 - либо в непустую последовательность букв A, либо в непустую последовательность букв B?

Пусть строка S1 состоит из цифр 0 и 1 и имеет длину N, а строка S2 (из символов A и B) - длину M.

Заведем матрицу А размера N на M, при этом строки матрицы помечаются i-ой цифрой строки S1, а j-й столбец - j-м символом строки S2.

Возьмем в качестве примера S1='00110', S2='AAAABBAA'.

Первая цифра строки S1 (цифра 0) может быть преобразована в одну из последовательностей букв 'A','AA','AAA','AAAA', являющиеся префиксами строки S2. Заносим символ 'x' в те столбцы первой строки, буквы-пометки которых соответствуют последним буквам возможных последовательностей. Таким образом, помечаются элементы A[1,1], A[1,2], A[1,3] и A[1,4].

Шаг алгоритма: будем преобразовывать очередную цифру S1[i], которой соответствует строка i.

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

Далее от места над последней помеченной ячейкой ищем в предыдущей строке 'x' и, когда находим, повторяем указанные выше операции.

Эти действия проводим далее для i=2,...,N.

#include <stdio.h>
#include <conio.h>
#include <string.h>
 
#define S1 "00110"
#define S2 "AAAABBAA"
#define N 5
#define M 8
 
int i, j;
char ctemp;
 
char A [N][M];
 
int main()
{
 
for (i=1; i<N; i++)
	for (j=1; j<M; j++)
 
		A[i][j] = ' '; // начальная инициализация 
		if (S1[1] == 0) ctemp = 'A'; // 0 -> A
		else ctemp = S2[1]; // 1 -> A || B
 
		i=1;
 
		while ((i <= M) && (S2[i] == ctemp))
		{
			A[1][i] = 'y';
			i++;
		}
 
	for (i=2; i<N; i++)
	{
		j=2;
 
		while (j<M)
		{
			if (A[i-1][j-1] == 'y')
			{
				if (S1[i] == 0) ctemp = 'A';
				else ctemp = S2[j];
 
				if (S2[j] == ctemp)
					while ((j<=M) && (S2[j] == ctemp))
					{
						A[i][j] = 'y';
						j++;
					}
				else j++;
			}	
			else j++;
		}
	}
 
 
if (A[N][M] == 'y') printf ("Можно преобразовать!\n");
	else printf("Нельзя преобразовать!\n");
 
getch();
return 0;
}