1829 - Cuvinte Ascunse

Enunt

Programatoarea Petra a început un curs de criptografie. Fiind un spirit creativ, Petra a creat deja o metodă elaborată de criptare a unei parole sub forma unei perechi (tabel de litere aparţinând mulţimii {‘a’...’z’}, dicţionar de cuvinte). Din păcate pentru Petra, metoda ei de criptare a parolei, poate fi decriptată de oricine astfel:

se iau tabelul de litere şi dicţionarul de cuvinte permise
se listează, sortează şi numără toate cuvintele care se găsesc în tabel. Un cuvânt c1c2…ck

care există în dicţionar există şi în tabel dacă fiecare literă ci
apare în tabel şi pentru i>1, ci
este vecină în tabel cu litera ci−1.

din lista sortata de T perechi (cuvânti, ai), unde cuvântieste un cuvânt iar ai este numărul de apariţii în tabel, reconstituie litera pi a parolei astfel: pi=‘a’ + ( aimod 26). Încercând să îmbunătăţească algoritmul, Petra a decis să înlocuiască unele litere din tabel cu semnul întrebării '?'. Un semn '?' poate fi înlocuit cu orice literă când se parcurge tabelul. Convinge-o pe Petra că, în ciuda îmbunătăţirii, îi poţi găsi parola pornind de la orice pereche de (dicţionar, tabel de litere) dată.

Cerinţa

Dat fiind un tabel de litere de dimensiuni N x M, şi o listă a cuvintelor din dicţionar, să se afişeze lista sortată de T perechi de forma 'ci: ai' şi parola Petrei.

Date de intrare

Fişierul cuvinteascunse.in va conţine N + C + 1 linii. Pe prima linie N, M, C – dimensiunile tabelului, şi numărul de cuvinte din dicţionar. Apoi cele N linii ale tabelului: t1,1 ...t1,m t2,1 ...t2,m . . . tn,1 ...tn,m urmate de cele C cuvinte din dicţionar, fiecare pe o linie: cuvânt1 cuvânt2 . . . cuvântC

Date de ieșire

Fişierul cuvinteascunse.out va conţine pe prima linie T, numărul de cuvinte distincte găsite în tabel. Pe următoarele T linii se vor afla perechi cuvânti ai separate printr-un spaţiu. Pe ultima linie se va afla un şir de caractere reprezentand parola Petrei.

Restricţii şi precizări

O secvenţă de litere reprezintă un cuvânt dacă se află în dicţionarul dat ca date de intrare. Dicţionarul conţine cuvinte formate din litere aparţinând mulţimii {‘a’...’z’}U{‘A’...’Z’}. Literele mici şi cele mari se consideră egale. Două litere sunt vecine în tabel, dacă celulele lor au o latura sau un colţ comun. Aceeaşi litera din tabel se poate folosi de mai multe ori într-un cuvânt. Dacă acelaşi semn '?' este folosit de mai multe ori într-un cuvânt, trebuie să reprezinte aceeaşi literă de fiecare dată.
0 < N < 6
0 < M < 6
0 < C < 20000

Exemplul 1

cuvinteascunse.in

 2 2 3
 e a
 l ?
 ea
 elena
 arc

cuvinteascunse.out

 2
 ea 3
 elena 1
 db

Explicație

Am gasit cuvântul “ea” de 3 ori: o data pe prima linie a tabelului, o data pe diagonala principală, inlocuind '?' cu 'a', şi o data ca “?a" inlocuind '?' cu 'e'. Am gasit cuvântul “elena” o data, inlocuind '?' cu 'n'.

Rezolvare

<syntaxhighlight lang="python" line> def is_valid_cell(i, j, n, m):

   return 0 <= i < n and 0 <= j < m

def search_word(grid, word, n, m, visited, i, j, idx):

   if idx == len(word):
       return True
   if not is_valid_cell(i, j, n, m) or visited[i][j] or grid[i][j] != word[idx]:
       return False
   visited[i][j] = True
   for di in [-1, 0, 1]:
       for dj in [-1, 0, 1]:
           if (di, dj) != (0, 0) and search_word(grid, word, n, m, visited, i + di, j + dj, idx + 1):
               return True
   visited[i][j] = False
   return False

def count_word_occurrences(grid, word, n, m):

   count = 0
   for i in range(n):
       for j in range(m):
           if grid[i][j] == word[0]:
               visited = [[False] * m for _ in range(n)]
               if search_word(grid, word, n, m, visited, i, j, 0):
                   count += 1
   return count

def main():

   with open("cuvinteascunse.in", "r") as fin:
       n, m, c = map(int, fin.readline().split())
       grid = [fin.readline().split() for _ in range(n)]
       words = [fin.readline().strip() for _ in range(c)]

   word_counts = {}
   for word in words:
       count = count_word_occurrences(grid, word, n, m)
       if count > 0:
           word_counts[word] = count

   sorted_words = sorted(word_counts.items(), key=lambda x: x[1], reverse=True)

   with open("cuvinteascunse.out", "w") as fout:
       fout.write(str(len(sorted_words)) + "\n")
       for word, count in sorted_words:
           fout.write(f"{word} {count}\n")
       password = ""
       for i in range(n):
           for j in range(m):
               if grid[i][j] != "?":
                   password += chr(ord("a") + (count_word_occurrences(grid, grid[i][j], n, m) % 26))
       fout.write(password + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>