TStringList *List = new TStringList;
char a[5][5];
char temp[5][5];
int pr[5][5];
int temp_pr[5][5];
int i,j,k,p,t;
int ai = i,aj = j; // Временные переменные для сохранения позиции в массиве
int curr;
String word;
bool bl;
bool tl;
List->LoadFromFile("word.txt");
for (i=0;i<5;i++)
for (j=0;j<5;j++)
a[j] = ' ';
memset(pr,0,sizeof(int)*5*5);
memset(temp_pr,0,sizeof(int)*5*5);
a[3][0] = 'п';
a[3][1] = 'а';
a[3][2] = 'р';
a[3][3] = 'т';
a[3][4] = 'а';
pr[3][0] = 2;
pr[3][1] = 2;
pr[3][2] = 2;
pr[3][3] = 2;
pr[3][4] = 2;
memcpy(temp_pr,pr,sizeof(int)*5*5);
curr = 0;
try
{
while (curr<List->Count)//Цикл по словарю
{
Application->ProcessMessages();
word = List->Strings[curr];
memcpy(pr,temp_pr,sizeof(int)*5*5);
tl = true;
for (k=1;k<word.Length();k++) //Цикл по слову из словаря
{
for (i=0;i<5;i++) // Цикл по самому массиву.
{
for (j=0;j<5;j++)
{
if (a[j]==' ')
{
for (ai=0;ai<5;ai++)
for (aj=0;aj<5;aj++)
temp[ai][aj] = a[ai][aj]; // сохранили массив, для возврата в предыдущее состояние.
a[j] = word[k];
bl = true;
p = k; // С какой буквы подставляли для поиска в конец слова
t = k; // С какой буквы подставляли для поиска в начало слова
ai = i;
aj = j;
memcpy(pr,temp_pr,sizeof(int)*5*5);
pr[j] = 1;
for (p = p+1;p<=word.Length();p++)
{
if (ai+1!=5)
if ((a[ai+1][aj]==word)&&(pr[ai+1][aj]!=1))
{
pr[ai+1][aj] = 1;
ai++;
continue;
}
if (ai-1!=-1)
if ((a[ai-1][aj]==word)&&(pr[ai-1][aj]!=1))
{
pr[ai-1][aj] = 1;
ai--;
continue;
}
if (aj+1!=5)
if ((a[ai][aj+1]==word)&&(pr[ai][aj+1]!=1))
{
pr[ai][aj+1] = 1;
aj++;
continue;
}
if (aj-1!=-1)
if ((a[ai][aj-1]==word)&&(pr[ai][aj-1]!=1))
{
pr[ai][aj-1] = 1;
aj--;
continue;
}
bl = false; // Если не совпало ни одно условие выше то это слово не подходит.
break;
}
ai = i;
aj = j;
if (bl)
{
for (t = t-1;t>0;t--)
{
if (ai+1!=5)
if ((a[ai+1][aj]==word[t])&&(pr[ai+1][aj]!=1))
{
pr[ai+1][aj] = 1;
ai++;
continue;
}
if (ai-1!=-1)
if ((a[ai-1][aj]==word[t])&&(pr[ai-1][aj]!=1))
{
pr[ai-1][aj] = 1;
ai--;
continue;
}
if (aj+1!=5)
if ((a[ai][aj+1]==word[t])&&(pr[ai][aj+1]!=1))
{
pr[ai][aj+1] = 1;
aj++;
continue;
}
if (aj-1!=-1)
if ((a[ai][aj-1]==word[t])&&(pr[ai][aj-1]!=1))
{
pr[ai][aj-1] = 1;
aj--;
continue;
}
bl = false; // Если не совпало ни одно условие выше то это слово не подходит.
break;
}
if (bl)
{
ListBox1->Items->Add(word);
for (ai=0;ai<5;ai++)
for (aj=0;aj<5;aj++)
a[ai][aj] = temp[ai][aj]; // восстановили массив, в текущем состоянии.
tl = false;
break; // Слово подошло переходим к следующему слову
}
}
for (ai=0;ai<5;ai++)
for (aj=0;aj<5;aj++)
a[ai][aj] = temp[ai][aj]; // восстановили массив, в текущем состоянии.
}
}
if (!tl)
break;
}
}
curr ++;
}
}
catch (...)
{
ShowMessage(word);
}
delete List;
[C] Перебор
Привет. Столкнулся с проблемой, немогу понять вчем дело. Вобщем есть алгоритм перебора слов (на доске 5х5 размещается слово и нужно подобрать все слова, путем подстановки буквы). Алгоритм работает в C++ Builder. Проблема возникла когда я пытался перенести на GCC компилер. На GCC почему-то алгоритм не неходит слов. Да, программа на GCC консольная, соответственно досовская кодировка там юзается, думал что проблема в этом, проверил вроде все нормально. Подскажите пожайлуста, что подправить и где, чтобы он работал в консольном варианте. Вот код:
в C++ Builder 6.0:
в C++ Builder 6.0:
Код:
Вот компилю на GCC или просто Borland C:
Словарик для теста прикрепил.
Код:
int main()
{
char a[5][5];
char temp[5][5];
int pr[5][5];
int temp_pr[5][5];
int i,j,k,p,t;
int ai = i,aj = j;
int curr;
char word[20];
bool bl;
bool tl;
FILE *file;
for (i=0;i<5;i++)
for (j=0;j<5;j++)
a[j] = ' ';
memset(pr,0,sizeof(int)*5*5);
memset(temp_pr,0,sizeof(int)*5*5);
a[3][0] = 'Є';
a[3][1] = '*';
a[3][2] = 'а';
a[3][3] = 'в';
a[3][4] = '*';
pr[3][0] = 2;
pr[3][1] = 2;
pr[3][2] = 2;
pr[3][3] = 2;
pr[3][4] = 2;
file = fopen("dictionary.dat", "r+");
rewind(file);
memcpy(temp_pr,pr,sizeof(int)*5*5);
curr = 0;
while (!feof(file))//Цикл по словарю
{
fscanf(file, "%s", &word);
memcpy(pr,temp_pr,sizeof(int)*5*5);
tl = true;
for (k=1;k<strlen(word);k++)
{
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
if (a[j]==' ')
{
for (ai=0;ai<5;ai++)
for (aj=0;aj<5;aj++)
temp[ai][aj] = a[ai][aj];
a[j] = word[k];
bl = true;
p = k;
t = k;
ai = i;
aj = j;
memcpy(pr,temp_pr,sizeof(int)*5*5);
pr[j] = 1;
for (p = p+1;p<=strlen(word);p++)
{
if (ai+1!=5)
if ((a[ai+1][aj]==word)&&(pr[ai+1][aj]!=1))
{
pr[ai+1][aj] = 1;
ai++;
continue;
}
if (ai-1!=-1)
if ((a[ai-1][aj]==word)&&(pr[ai-1][aj]!=1))
{
pr[ai-1][aj] = 1;
ai--;
continue;
}
if (aj+1!=5)
if ((a[ai][aj+1]==word)&&(pr[ai][aj+1]!=1))
{
pr[ai][aj+1] = 1;
aj++;
continue;
}
if (aj-1!=-1)
if ((a[ai][aj-1]==word)&&(pr[ai][aj-1]!=1))
{
pr[ai][aj-1] = 1;
aj--;
continue;
}
bl = false;
break;
}
ai = i;
aj = j;
if (bl)
{
for (t = t-1;t>0;t--)
{
if (ai+1!=5)
if ((a[ai+1][aj]==word[t])&&(pr[ai+1][aj]!=1))
{
pr[ai+1][aj] = 1;
ai++;
continue;
}
if (ai-1!=-1)
if ((a[ai-1][aj]==word[t])&&(pr[ai-1][aj]!=1))
{
pr[ai-1][aj] = 1;
ai--;
continue;
}
if (aj+1!=5)
if ((a[ai][aj+1]==word[t])&&(pr[ai][aj+1]!=1))
{
pr[ai][aj+1] = 1;
aj++;
continue;
}
if (aj-1!=-1)
if ((a[ai][aj-1]==word[t])&&(pr[ai][aj-1]!=1))
{
pr[ai][aj-1] = 1;
aj--;
continue;
}
bl = false;
break;
}
if (bl)
{
printf("%s\n", word);
for (ai=0;ai<5;ai++)
for (aj=0;aj<5;aj++)
a[ai][aj] = temp[ai][aj];
tl = false;
break;
}
}
for (ai=0;ai<5;ai++)
for (aj=0;aj<5;aj++)
a[ai][aj] = temp[ai][aj];
}
}
if (!tl)
break;
}
}
curr ++;
}
}
{
char a[5][5];
char temp[5][5];
int pr[5][5];
int temp_pr[5][5];
int i,j,k,p,t;
int ai = i,aj = j;
int curr;
char word[20];
bool bl;
bool tl;
FILE *file;
for (i=0;i<5;i++)
for (j=0;j<5;j++)
a[j] = ' ';
memset(pr,0,sizeof(int)*5*5);
memset(temp_pr,0,sizeof(int)*5*5);
a[3][0] = 'Є';
a[3][1] = '*';
a[3][2] = 'а';
a[3][3] = 'в';
a[3][4] = '*';
pr[3][0] = 2;
pr[3][1] = 2;
pr[3][2] = 2;
pr[3][3] = 2;
pr[3][4] = 2;
file = fopen("dictionary.dat", "r+");
rewind(file);
memcpy(temp_pr,pr,sizeof(int)*5*5);
curr = 0;
while (!feof(file))//Цикл по словарю
{
fscanf(file, "%s", &word);
memcpy(pr,temp_pr,sizeof(int)*5*5);
tl = true;
for (k=1;k<strlen(word);k++)
{
for (i=0;i<5;i++)
{
for (j=0;j<5;j++)
{
if (a[j]==' ')
{
for (ai=0;ai<5;ai++)
for (aj=0;aj<5;aj++)
temp[ai][aj] = a[ai][aj];
a[j] = word[k];
bl = true;
p = k;
t = k;
ai = i;
aj = j;
memcpy(pr,temp_pr,sizeof(int)*5*5);
pr[j] = 1;
for (p = p+1;p<=strlen(word);p++)
{
if (ai+1!=5)
if ((a[ai+1][aj]==word)&&(pr[ai+1][aj]!=1))
{
pr[ai+1][aj] = 1;
ai++;
continue;
}
if (ai-1!=-1)
if ((a[ai-1][aj]==word)&&(pr[ai-1][aj]!=1))
{
pr[ai-1][aj] = 1;
ai--;
continue;
}
if (aj+1!=5)
if ((a[ai][aj+1]==word)&&(pr[ai][aj+1]!=1))
{
pr[ai][aj+1] = 1;
aj++;
continue;
}
if (aj-1!=-1)
if ((a[ai][aj-1]==word)&&(pr[ai][aj-1]!=1))
{
pr[ai][aj-1] = 1;
aj--;
continue;
}
bl = false;
break;
}
ai = i;
aj = j;
if (bl)
{
for (t = t-1;t>0;t--)
{
if (ai+1!=5)
if ((a[ai+1][aj]==word[t])&&(pr[ai+1][aj]!=1))
{
pr[ai+1][aj] = 1;
ai++;
continue;
}
if (ai-1!=-1)
if ((a[ai-1][aj]==word[t])&&(pr[ai-1][aj]!=1))
{
pr[ai-1][aj] = 1;
ai--;
continue;
}
if (aj+1!=5)
if ((a[ai][aj+1]==word[t])&&(pr[ai][aj+1]!=1))
{
pr[ai][aj+1] = 1;
aj++;
continue;
}
if (aj-1!=-1)
if ((a[ai][aj-1]==word[t])&&(pr[ai][aj-1]!=1))
{
pr[ai][aj-1] = 1;
aj--;
continue;
}
bl = false;
break;
}
if (bl)
{
printf("%s\n", word);
for (ai=0;ai<5;ai++)
for (aj=0;aj<5;aj++)
a[ai][aj] = temp[ai][aj];
tl = false;
break;
}
}
for (ai=0;ai<5;ai++)
for (aj=0;aj<5;aj++)
a[ai][aj] = temp[ai][aj];
}
}
if (!tl)
break;
}
}
curr ++;
}
}
Словарик для теста прикрепил.
Воспользуйтесь дебаггером-то
Непомогает. Вот пробую сделать рекурсивно, но возникает ошибка, подправьте плиз:
Код:
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
char Ab[34] = "*ЎўЈ¤Ґс¦§Ё©Є«¬*®Їабвгдежзийклмноп"; // алфавит
char Board[5][5]; // поле
char Prohod[5][5]; // пройденные клетки. Когда прошли клетку x, y то ставим 1.
FILE* File;
char WordExists(char Str[20])
{
char tmp[20];
char f;
while (!feof(File))
{
fscanf(File, "%s", &tmp);
if (strcmpi(tmp, Str) == 0)
{
f = 1;
break;
}
else
{
f = 0;
}
return f;
}
}
char GB(int x, int y) // граница поля, если выходит за границу возвращаем 1, иначе 0
{
if ((x >= 0) && (x <= 5) && (y >= 0) && (y <= 5))
return 0;
else
return 1;
}
char CharHere(int x, int y) // есть ли буква рядом от позиции x, y
{
if (!GB(x+1, y) && (Board[x+1][y]) || // если не выходим за пределы поля и в клетке есть буква.
!GB(x-1, y) && (Board[x-1][y]) || // осматриваем по разные стороны от текущих координат
!GB(x, y+1) && (Board[x][y+1]) ||
!GB(x, y-1) && (Board[x][y-1]))
return 1;
else
return 0;
}
char FAW(char M[5][5], int x, int y, int x1, int y1, int max, char r[20])
{
static int cnt = -1;
if (strlen(r) > max)
return 0;
cnt++;
r[cnt] = M[x][y];
r[cnt+1] = '\0';
Prohod[x1][y1] = 1; // вот сдесь возникает ошибка
if (WordExists(r) && !Prohod[x1][y1])
{
printf("%s\n", r);
memcpy(Prohod, 0, sizeof(Prohod));
}
if (!GB(x+1, y) && Prohod[x1][y1])
FAW(M, x+1, y, x1, y1, max, r);
if (!GB(x-1, y) && Prohod[x1][y1])
FAW(M, x+1, y, x1, y1, max, r);
if (!GB(x, y+1) && Prohod[x1][y1])
FAW(M, x, y+1, x1, y1, max, r);
if (!GB(x, y-1) && Prohod[x1][y1])
FAW(M, x, y-1, x1, y1, max, r);
}
void FindWords(void/*char Words[20][20], char MP[20][20], int WordLen*/)
{
int i, j;
int cr;
int n, m;
char a[5];
char r[20];
for (i = 0; i < 5; i++)
{
for (j = 0; j < 5; j++)
{
if (!Board[j] && CharHere(i, j)) // нашли подходящую пустую клетку
{
for (cr = 0; cr < 34; cr++)
{
Board[j] = Ab[cr]; // ставим букву на поле и запускаем рекурсию
for (n = 0; n < 5; n++)
{
for (m = 0; m < 5; m++)
{
FAW(Board, i, j, n, m, 24, r);
}
}
Board[j] = ' ';
}
}
}
}
}
int main()
{
Board[0][3] = 'Є';
Board[1][3] = '*';
Board[2][3] = 'а';
Board[3][3] = 'в';
Board[4][3] = '*';
File = fopen("word.txt", "r");
FindWords();
}
#include <string.h>
#include <conio.h>
#include <stdlib.h>
char Ab[34] = "*ЎўЈ¤Ґс¦§Ё©Є«¬*®Їабвгдежзийклмноп"; // алфавит
char Board[5][5]; // поле
char Prohod[5][5]; // пройденные клетки. Когда прошли клетку x, y то ставим 1.
FILE* File;
char WordExists(char Str[20])
{
char tmp[20];
char f;
while (!feof(File))
{
fscanf(File, "%s", &tmp);
if (strcmpi(tmp, Str) == 0)
{
f = 1;
break;
}
else
{
f = 0;
}
return f;
}
}
char GB(int x, int y) // граница поля, если выходит за границу возвращаем 1, иначе 0
{
if ((x >= 0) && (x <= 5) && (y >= 0) && (y <= 5))
return 0;
else
return 1;
}
char CharHere(int x, int y) // есть ли буква рядом от позиции x, y
{
if (!GB(x+1, y) && (Board[x+1][y]) || // если не выходим за пределы поля и в клетке есть буква.
!GB(x-1, y) && (Board[x-1][y]) || // осматриваем по разные стороны от текущих координат
!GB(x, y+1) && (Board[x][y+1]) ||
!GB(x, y-1) && (Board[x][y-1]))
return 1;
else
return 0;
}
char FAW(char M[5][5], int x, int y, int x1, int y1, int max, char r[20])
{
static int cnt = -1;
if (strlen(r) > max)
return 0;
cnt++;
r[cnt] = M[x][y];
r[cnt+1] = '\0';
Prohod[x1][y1] = 1; // вот сдесь возникает ошибка
if (WordExists(r) && !Prohod[x1][y1])
{
printf("%s\n", r);
memcpy(Prohod, 0, sizeof(Prohod));
}
if (!GB(x+1, y) && Prohod[x1][y1])
FAW(M, x+1, y, x1, y1, max, r);
if (!GB(x-1, y) && Prohod[x1][y1])
FAW(M, x+1, y, x1, y1, max, r);
if (!GB(x, y+1) && Prohod[x1][y1])
FAW(M, x, y+1, x1, y1, max, r);
if (!GB(x, y-1) && Prohod[x1][y1])
FAW(M, x, y-1, x1, y1, max, r);
}
void FindWords(void/*char Words[20][20], char MP[20][20], int WordLen*/)
{
int i, j;
int cr;
int n, m;
char a[5];
char r[20];
for (i = 0; i < 5; i++)
{
for (j = 0; j < 5; j++)
{
if (!Board[j] && CharHere(i, j)) // нашли подходящую пустую клетку
{
for (cr = 0; cr < 34; cr++)
{
Board[j] = Ab[cr]; // ставим букву на поле и запускаем рекурсию
for (n = 0; n < 5; n++)
{
for (m = 0; m < 5; m++)
{
FAW(Board, i, j, n, m, 24, r);
}
}
Board[j] = ' ';
}
}
}
}
}
int main()
{
Board[0][3] = 'Є';
Board[1][3] = '*';
Board[2][3] = 'а';
Board[3][3] = 'в';
Board[4][3] = '*';
File = fopen("word.txt", "r");
FindWords();
}
Цитата: xface
Непомогает.
Такого не может быть. Найдите место с которого начинаются проблемы, тогда будем разбираться
Цитата: Phodopus
Такого не может быть. Найдите место с которого начинаются проблемы, тогда будем разбираться
Мне бы хотелось доработать рикурсивный вариант. Щас может что сделаю. Я уже тут несколько проблем обнаружил. Правильно ли я делаю:
Pascal:
Код:
...
r: String;
M: Array[0..5][0..5] of Char;
r := r + M[x][y];
...
r: String;
M: Array[0..5][0..5] of Char;
r := r + M[x][y];
...
C
Код:
...
char r[20];
char M[5][5];
int c = -1;
c++;
r[c] = M[x][y];
r[c+1] = '\0';
...
char r[20];
char M[5][5];
int c = -1;
c++;
r[c] = M[x][y];
r[c+1] = '\0';
...
Мне кажется на С не так будет. А вот как х3(
Код:
[COLOR="Red"]int c = -1;
c++;
r[c] = M[x][y];
r[c+1] = '\0';[/COLOR]
c++;
r[c] = M[x][y];
r[c+1] = '\0';[/COLOR]
это типо цикл что ли ? Я чего то не понял чего ты там хотел написать
Попробуй погуглить функцию CharToOem для gcc
Цитата: cronya
Код:
[COLOR="Red"]int c = -1;
c++;
r[c] = M[x][y];
r[c+1] = '\0';[/COLOR]
c++;
r[c] = M[x][y];
r[c+1] = '\0';[/COLOR]
это типо цикл что ли ? Я чего то не понял чего ты там хотел написать
Попробуй погуглить функцию CharToOem для gcc
Я хотел написать сложение символов в строку. Т.е помещаем символ по индексу c++, и в конце строки ставим нуль-терминант. Тут я поправил, сделав c++ глобальной переменной. Но проблеме терь в другом, функция работает не правильно (