Vizualizare sursă pentru „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ânti
 este un cuvânt iar ai
 este numărul de apariţii în tabel, reconstituie litera pi
 a parolei astfel: pi=
 ‘a’ + ( ai
  mod 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'.
<br>


== 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>