Алгоритм слова Boggle в C#
Я пытаюсь решить тест на умение в CodeFights, и я столкнулся с проблемой, когда пытался решить алгоритм словосочетания. вот описание задачи:
Boggle - популярная игра в слова, в которой игроки пытаются найти слова в последовательности соседних букв на прямоугольной доске.
Имея двумерную матричную доску, которая представляет ячейки символов доски Boggle и массив уникальных строк слов, найдите все возможные слова из слов, которые могут быть сформированы на доске.
Обратите внимание, что в Boggle, когда вы находите слово, вы можете перейти от ячейки к любому из ее 8 соседей, но вы не можете использовать одну и ту же ячейку дважды в одном слове.
Я написал код, который выглядит так, как будто он работает, однако он не проходит скрытый тест, который у них есть, и теперь я застрял на этом этапе.
Вот мой код:
string[] wordBoggle(char[][] board, string[] words)
{
string[] foundWords = new string[words.Length];
for (int i = 0; i < words.Length; i++)
{
List<int[]> Prefixs = new List<int[]>();
for (int j = 0; j < board.Length; j++)
{
for (int k = 0; k < board[j].Length; k++)
{
if (board[j][k] == words[i][0])
{
int[] match = new int[] { j, k };
Prefixs.Add(match);
}
}
}
if (Prefixs.Count > 0)
{
for (int l = 0; l < Prefixs.Count; l++)
{
bool[][] bitMap = new bool[board.Length][];
ResetBitMap(bitMap, board.Length, board[0].Length);
bitMap[Prefixs[l][0]][Prefixs[l][1]] = true;
bool match = search(Prefixs[l][0], Prefixs[l][1], board, words[i], bitMap, 1);
if (match)
{
foundWords[i] = words[i];
break;
}
}
}
}
var res = foundWords.Where(q => q != null).OrderBy(e => e).Distinct().ToArray();
return res;
}
bool search(int col, int row, char[][] board, string word, bool[][] bitMap, int index)
{
var found = false;
if (index == word.Length)
{
return true;
}
Dictionary<int[], char> neighbors = getNeightbors(col, row, board);
var allNextMatchs = neighbors.Where(a => a.Value == word[index]).ToArray();
if (allNextMatchs.Length < 1 && index < word.Length - 1)
{
return false;
}
var count = 0;
for (int i = 0; i < bitMap.Length; i++)
{
for (int k = 0; k < bitMap[i].Length; k++)
{
if (bitMap[i][k] == true)
{
count++;
}
}
}
if (count == word.Length)
{
return true;
}
foreach (var item in allNextMatchs)
{
if (item.Value != 0 && bitMap[item.Key[0]][item.Key[1]] == false)
{
col = item.Key[0];
row = item.Key[1];
bitMap[col][row] = true;
if (index < word.Length - 1)
{
index += 1;
}
found = search(col, row, board, word, bitMap, index);
if (found)
{
return true;
}
else
{
ResetBitMap(bitMap, board.Length, board[0].Length);
}
}
else
{
continue;
}
}
return found;
}
Dictionary<int[], char> getNeightbors(int col, int row, char[][] board)
{
Dictionary<int[], char> neighbors = new Dictionary<int[], char>(8);
try
{
int[] cr = new int[] { col - 1, row - 1 };
neighbors.Add(cr, board[col - 1][row - 1]); ; // left up
}
catch (IndexOutOfRangeException e) {
Console.WriteLine(e.Message);
}
try
{
int[] cr = new int[] { col, row - 1 };
neighbors.Add(cr, board[col][row - 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col + 1, row - 1 };
neighbors.Add(cr, board[col + 1][row - 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col - 1, row };
neighbors.Add(cr, board[col - 1][row]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col + 1, row };
neighbors.Add(cr, board[col + 1][row]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col + 1, row + 1 };
neighbors.Add(cr, board[col + 1][row + 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col, row + 1 };
neighbors.Add(cr, board[col][row + 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
try
{
int[] cr = new int[] { col - 1, row + 1 };
neighbors.Add(cr, board[col - 1][row + 1]);
}
catch (IndexOutOfRangeException e) { Console.WriteLine(e.Message); }
return neighbors;
}
void ResetBitMap(bool[][] map, int col, int row)
{
for (int i = 0; i < map.Length; ++i)
{
map[i] = new bool[row];
}
for (int j = 0; j < map.Length; ++j)
{
for (int k = 0; k < map[0].Length; ++k)
{
map[j][k] = false;
}
}
}
Кто-нибудь знает, что я здесь скучаю?
1 ответ
У меня есть решение, следуйте обратитесь:
int Arrtick[4][4];
void BT(vector<std::vector<char>> boggle, string words,int lengOfword, int N, int x, int y, int currID, bool &flag)
{
if (currID >= lengOfword){
flag = true; return;
}
//1.
if (y + 1 < N && boggle[x][y + 1] == words[currID] && Arrtick[x][y + 1] == 0)
{
Arrtick[x][y + 1] = 1;
BT(boggle, words, lengOfword, N, x, y + 1, currID + 1, flag);
Arrtick[x][y + 1] = 0;
}
if (flag) return;
//2.
if (x + 1 < N && y + 1 < N && boggle[x + 1][y + 1] == words[currID] && Arrtick[x + 1][y + 1] == 0)
{
Arrtick[x + 1][y + 1] = 1;
BT(boggle, words, lengOfword, N, x + 1, y + 1, currID + 1, flag);
Arrtick[x + 1][y + 1] = 0;
}
if (flag) return;
//3.
if (x + 1 < N && boggle[x + 1][y] == words[currID] && Arrtick[x + 1][y] == 0)
{
Arrtick[x + 1][y] = 1;
BT(boggle, words, lengOfword, N, x + 1, y, currID + 1, flag);
Arrtick[x + 1][y] = 0;
}
if (flag) return;
//4.
if (x + 1 < N && y - 1 >= 0 && boggle[x + 1][y - 1] == words[currID] && Arrtick[x + 1][y - 1] == 0)
{
Arrtick[x + 1][y - 1] = 1;
BT(boggle, words, lengOfword, N, x + 1, y - 1, currID + 1, flag);
Arrtick[x + 1][y - 1] = 0;
}
if (flag) return;
//5.
if (y - 1 >= 0 && boggle[x][y - 1] == words[currID] && Arrtick[x][y - 1] == 0)
{
Arrtick[x][y - 1] = 1;
BT(boggle, words, lengOfword, N, x, y - 1, currID + 1, flag);
Arrtick[x][y - 1] = 0;
}
if (flag) return;
//6.
if (x - 1 >= 0 && y - 1 >= 0 && boggle[x - 1][y - 1] == words[currID] && Arrtick[x - 1][y - 1] == 0)
{
Arrtick[x - 1][y - 1] = 1;
BT(boggle, words, lengOfword, N, x - 1, y - 1, currID + 1, flag);
Arrtick[x - 1][y - 1] = 0;
}
if (flag) return;
//7.
if (x - 1 >= 0 && boggle[x - 1][y] == words[currID] && Arrtick[x - 1][y] == 0)
{
Arrtick[x - 1][y] = 1;
BT(boggle, words, lengOfword, N, x - 1, y, currID + 1, flag);
Arrtick[x - 1][y] = 0;
}
if (flag) return;
//8.
if (x - 1 >= 0 && y + 1 < N && boggle[x - 1][y + 1] == words[currID] && Arrtick[x - 1][y + 1] == 0)
{
Arrtick[x - 1][y + 1] = 1;
BT(boggle, words, lengOfword, N, x - 1, y + 1, currID + 1, flag);
Arrtick[x - 1][y + 1] = 0;
}
}
// Prints all words present in dictionary.
std::vector<std::string> wordBoggle(std::vector<std::vector<char>> boggle, std::vector<std::string> words)
{
int Nx = boggle[0].size();
int Ny = boggle.size();
bool flagg;
vector<std::string> strOutput;
for (int k = 0; k < words.size(); k++)
{
flagg = false;
memset(Arrtick, 0, sizeof(Arrtick));
for (int i = 0; i < Nx; i++)
{
for (int j = 0; j < Ny; j++)
{
if (boggle[i][j] == words[k][0])
{
Arrtick[i][j] = 1;
BT(boggle, words[k], words[k].size(), Nx, i, j, 1, flagg);
Arrtick[i][j] = 0;
}
if (flagg)
break;
}
if (flagg)
{
strOutput.push_back(words[k]);
break;
}
}
}
return strOutput;
}