Any ideas? Perhaps finding a path in the graph?

The first line of input contains the word that you need to find on the field. The word length is from 1 to 25 characters. The next 5 lines contain 5 characters each - the field of philvord. The field size is always 5 by 5. Output Y or N depending on whether the word is found or not. The letters in the word can be placed as you like, except on the diagonal

Entered:

WORD WRDYM FOHHH NLKWO RRRRR ABBCD

Brought: Y

  • What have you done? Why did you decide that you should write code for you? - And
  • This question is something fundamentally different from ru.stackoverflow.com/questions/972989 ? - gil9red pm
  • Possible duplicate question: Difficult task. What kind of algorithm? - And
  • @ gil9red, only by the fact that it is impossible to answer the questions that require editing;) - MaxU
  • Not a code. Do you think everyone should also write a quick exponentiation or a sieve of Eratosthenes themselves, without getting a ready idea? I need not a ready-made solution, but the idea of ​​an algorithm, or at least the desired topic. - Viktor Yamschin

1 answer 1

Normal graph traversal. I would use DFS. We go to the next peak only if the next letter suits us. As a used array, we use a three-dimensional array with a third dimension - the index of the letter in the search word.

 var a = [ " ", " WRDYM ", " FOHHH ", " NLKWO ", " RRRRR ", " ABBCD ", " ", ] var s = "WORD" var used = a.map(x => [...x].map(x => Array(s.length))) var di = [0, 0, 1, -1], dj = [1, -1, 0, 0] var path = [] function dfs(i, j, k=0) { if (a[i][j] === s[k] && !used[i][j][k]) { used[i][j][k] = true path.push({i, j}) if (++k === s.length) return true for (var q=0; q<4; ++q) { if (dfs(i+di[q], j+dj[q], k)) { return true } } path.pop() } } ALL: for (var q=1; q<a.length-1; ++q) { for (var w=1; w<a[q].length-1; ++w) { if (dfs(q, w)) { console.log(path.map(({i, j}) => `(${i}, ${j})`).join("\n")) break ALL } } }

  • And what if there are two options with the appropriate two letters in a row, and in one the third is not correct? We are looking for elements that coincide with the letters in the word only through one - Victor Yamschin
  • @ Viktor Yamschin, so dfs will bypass all options until it finds one. - Qwertiy ♦ 3:53 pm
  • Yes, but he is looking for a way, does not consider whether the next vertex is suitable for us or not, where will we keep the peak at which we “stopped”? - Victor Yamschin
  • And yet, to implement DFS you need an adjacency list, how can it be compiled for such a task? - Victor Yamschin
  • @ Viktor Yamschin, not needed. Before proceeding, check its validity. - Qwertiy ♦ 4:16 pm