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…ckcare există în dicţionar există şi în tabel dacă fiecare literă ci apare în tabel şi pentru i>1, cieste 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

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()