Hola, vuelvo a pasar por acá para hacer un pregunta sobre un problema del juez de la OIA. Quise ponerme a hacer el problema Juego con Letras, del Certamen Nacional 2011, de nivel 2 (http://juez.oia.unsam.edu.ar/#/task/rapigrama/statement)
Después de un par de intentos logré a llegar hasta los 65/100 ptos, siendo dos los casos en los cuales mi solución no funciona (siendo uno de ellos el de amyor puntaje).
Para resolver el problema, realizo lo siguiente:
- Dadas las palabras, guardo la primera letra de las mismas en un set. A su vez, asigno para cada una de tales letras, el prefijo formado por las dos primeras letras de la palabra. Finalmente asigno según tales prefijos, una lista con las palabras originales para cada uno (comprendo que podría hacer un set con todas las palabras, pero resulta que hacer esto ahorra un poco de tiempo de ejecución). Además, para luego poder dar el resultado, hago un mapa donde guardo los índices de las palabras. Como pueden repetirse, por cada una le asigno un vector con los índices de todas las existentes.
- Recorro el tablero fijándome si alguna de las letras coincide con el comienzo de alguna de mis palabras.
- Si encuentro una letra que potencialmente sea el comienzo de alguna palabra de la lista, me fijo hacia cada uno de los sentidos de la misma, por la letra adyacente. Si el prefijo formado por la letra en mi posición y el de aquella adyacente que encuentre, continúo en la dirección que la encontré.
- A medida que avanzo por la dirección mencionada, voy formando una palabra agregando cada letra por la que paso. En cada vuelta, verifico si la palabra que tengo hasta el momento forma parte de mi lista. Paro de buscar cuando llego a alguno de los bordes de la cuadrícula (he pensado en dejar de buscar si lo que tengo no coincide, aunque no sé cómo podría implementar eso, además de que ocuparía bastante memoria).
- En caso de encontrar una palabra, guardo los índices según las palabras (descartando luego ese índice de mi lista por la palabra) y la dirección. Cuando termino de buscar, ordeno los resultados en función de los números. Ya ordenados, los imprimo en pantalla.
Tengo entendido que debe de haber un problema en la implementación. Espero me puedan ayudar. Dejo mi código:
Código
#include <bits/stdc++.h>
#define forn(i,n) for(int i = 0; i < int(n); i++)
#define fst first
#define snd second
using namespace std;
typedef vector<string> vs;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int X[] = {0,-1,0,1};
const int Y[] = {1,0,-1,0};
struct sorter {
int num;
char d;
bool operator<(const sorter &a) const{
return a.num > num;
}
};
vs rapi;
set<char> yes;
map<char,set<string> > prim;
map<string, set<string> > sec;
map<string, vi> refers;
map<ii,char> dir;
vector<sorter> resultado;
void init();
char way(int &x, int &y, int &posX, int &posY);
bool valido(int &x, int &y);
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int D,P;
freopen("rapigrama.in","r",stdin);
freopen("rapigrama.out","w",stdout);
init();
cin >> D >> P;
forn (i,D) {
string x;
cin >> x;
rapi.push_back(x);
}
forn (i,P) {
string x,aux;
cin >> x;
aux+=x[0];
aux+=x[1];
prim[x[0]].insert(aux);
sec[aux].insert(x);
refers[x].push_back(i+1);
yes.insert(x[0]);
}
forn (m,rapi.size()) {
forn (n,rapi[0].size()) {
char j = rapi[m][n];
if (yes.count(j)) {
forn (i,4) {
string aux;
aux+=j;
int tendX = X[i];
int tendY = Y[i];
int x = n+tendX;
int y = m+tendY;
if (!valido(x,y)) continue;
aux+=rapi[y][x];
if (prim[j].count(aux)) {
string act = aux;
while (true) {
if (sec[act].count(aux) and not refers[aux].empty()) {
int m = refers[aux].back();
refers[aux].pop_back();
resultado.push_back({m,way(tendX,tendY,x,y)});
break;
}
char direct = way(tendX,tendY,x,y);
if (not valido(x,y)) break;
aux += rapi[y][x];
}
}
}
}
}
}
sort (resultado.begin(),resultado.end());
for (auto &i : resultado) {
cout << i.num << ' ' << i.d << '\n';
}
return 0;
}
void init() {
dir[{0,1}] = 'S';
dir[{-1,0}] = 'O';
dir[{0,-1}] = 'N';
dir[{1,0}] = 'E';
}
char way(int &x, int &y, int &posX, int &posY) {
char c = dir[{x,y}];
switch (c) {
case 'N' : posY--; break;
case 'S' : posY++; break;
case 'O' : posX--; break;
case 'E' : posX++; break;
}
return c;
}
bool valido (int &x, int &y) {
if (x < 0 or y < 0) return false;
if (y >= rapi.size() or x >= rapi[0].size()) return false;
return true;
}
! Aunque tendrías que tener en claro qué cosas ponés y qué cosas buscás.