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 \(c_1c_2:::c_k\) care există în dicţionar există şi în tabel dacă, fiecare literă ci apare în tabel şi pentru i>1, \(c_i\) este vecină în tabel cu litera \(c_{i-1}\).
din lista sortata de T perechi (\(cuvânt_i\), \(a_i\)), unde \(cuvânt_i\) este un cuvânt iar \(a_i\) este numărul de apariţii în tabel, reconstituie litera \(p_i\) a parolei astfel: \(p_i =\) ‘a’ + ( \(a_i\) 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:
\(t_1,1:::t_1,m\)
. . .
\(t_n,1:::t_n,m\)
urmate de cele C cuvinte din dicţionar, fiecare pe o linie:
\(cuvânt_1\)
. . .
\(cuvânt_C\)

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

Exemplu

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'.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema CuvinteAscunse:

#include <stdio.h>
#include <vector>
#include <string>
#include <string.h>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

#define N_MAX 6
#define M_MAX 6
#define C_MAX 200
#define A_SIZE 26  // alphabet size

char tab[N_MAX][C_MAX];
int N, M, C;

struct TrieNode {
  // chs: cele 26 de litere din alfabet
  TrieNode* chs[A_SIZE];
  // count: informatie despre cuvantul de la radcina pana la nod
  // -1 cuvantul *nu* e in dictionar
  //  0 cuvantul e in dictionar
  // > 0 cuvantul e in dictionar si apare de count ori
  int count;

  TrieNode() {
    count = -1;
    memset(chs, 0, A_SIZE * sizeof(struct TrieNode*));
  }

  void insert(string cuv);
  void print_and_collect(fstream &fout, string cuv, int min_count, vector<int> &counts);
  void count_words(int& n_cuv, int min_count);
};

void TrieNode::insert(string cuv) {
  TrieNode* tn = this;
  int clen = cuv.length();
  for (int i = 0; i < clen; i++) {
      int idx = cuv[i] - 'a';
      if (tn->chs[idx] == NULL ) {
        tn->chs[idx] = new TrieNode();
      }
      tn = tn->chs[idx];
  }
  // ultima litera din cuvant
  tn->count = 0;
}

void TrieNode::count_words(int& n_cuv, int min_count) {
  TrieNode* tn = this;
  if (tn == NULL)
    return;

  if (tn->count >= min_count) {
    n_cuv = n_cuv + 1;
  }

  for(int i = 0; i < A_SIZE; i++) {
    tn->chs[i]->count_words(n_cuv, min_count);
  }
}

void TrieNode::print_and_collect(fstream &fout, string cuv, int min_count, vector<int> &counts) {
  TrieNode* tn = this;
  if (tn == NULL)
    return;
  if (tn->count >= min_count) {
    fout << cuv << " " << tn->count << "\n";
    counts.push_back(tn->count);
  }
  for(int i = 0; i < A_SIZE; i++) {
    cuv.push_back('a' + i);
    tn->chs[i]->print_and_collect(fout, cuv, min_count, counts);
    cuv.erase(cuv.end() - 1, cuv.end());
  }
}

void print_solution(fstream &fout, TrieNode &dict, int min_count) {
  string s;
  vector<int> counts;
  int n_words = 0;
  dict.count_words(n_words, min_count);
  fout << n_words << "\n";

  dict.print_and_collect(fout, s, min_count, counts);

  vector<int>::iterator it;
  for(it = counts.begin(); it != counts.end(); it++) {
    fout << (char)('a' + (*it % 26))  ;
  }
  fout << "\n";
}

bool in_bounds(int x, int y) {
  return (x >= 0 && y >= 0 && x < N && y < M);
}

void dfs(TrieNode *dict, int i, int j) {
  int idx_l = tab[i][j] - 'a';
  int idx_r = tab[i][j] - 'a' + 1;
  if (tab[i][j] == '?') {
    idx_l = 0;
    idx_r = A_SIZE;
  }

  int old_ij = tab[i][j];
  for(int idx = idx_l; idx < idx_r; idx ++ ) {
    tab[i][j] = 'a' + idx;

    TrieNode* cur_tn = dict->chs[idx];
    if(cur_tn == NULL)
      continue;

    // increase current word
    if(cur_tn->count >= 0) {
      cur_tn->count++;
    }

    for(int dx = -1; dx < 2; dx++){
      for(int dy = -1; dy < 2; dy++){
        if((dx == 0 && dy == 0) || !in_bounds(i + dx, j + dy))
          continue;

        dfs(cur_tn, i + dx, j + dy);
      }
    }
  }
  tab[i][j] = old_ij;
}

int main() {
  int i, j;
  fstream fin, fout;
  fin.open("cuvinteascunse.in", fstream::in);
  fout.open("cuvinteascunse.out", fstream::out);
  fin >> N >> M >> C;
  for(i = 0; i < N; i++)
    for(j = 0; j < M; j++)
      fin >> tab[i][j];

  TrieNode dict;
  string cuv;
  for(i = 0; i < C; i++){
    fin >> cuv;
    std::transform(cuv.begin(), cuv.end(),cuv.begin(), ::tolower);
    dict.insert(cuv);
  }

  for(i = 0; i < N; i++)
    for(j = 0; j < M; j++)
      dfs(&dict, i, j);

  print_solution(fout, dict, 1);

  fin.close();
  fout.close();
  return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1829 CuvinteAscunse

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1829 CuvinteAscunse de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1829 CuvinteAscunse