Hola!
La idea es reorganizar un poco los envíos de problemas.
Estos problemas estan enmarcados en la técnica/algoritmo BFS (wiki) .
Enviamos entonces problemas que queremos que enfrenten con esta técnica, en orden creciente de dificultad
En el problema 3, como es el nombre de la input file? Porque no dice en ningun lado y cuando submiteo me da error de runtime.
Por las dudas, mi código:
#include <bits/stdc++.h>
using namespace std;
struct Pos {
int x;
int y;
Pos(int x, int y): x(x), y(y) {}
};
Pos operator+(Pos a, Pos b) {
return Pos(a.x + b.x, a.y + b.y);
}
bool in_bounds(int x, int n) {
return x >= 0 && x < n;
}
//int calc(int a, int c, vector<vector<char>> keys, string s) {
int calc() {
vector<Pos> neis = {Pos(1, 0), Pos(0, 1), Pos(-1, 0), Pos(0, -1)};
int r, c;
cin >> r >> c;
vector<vector<char>> keys(c, vector<char>(r));
for(int y = 0; y < r; ++y) {
for(int x = 0; x < c; ++x) {
cin >> keys[x][y];
}
//char nline;
//cin >> nline;
}
string s;
cin >> s;
s.push_back('*');
vector<vector<int>> max_match(c, vector<int>(r, -333333333));
max_match[0][0] = 0;
vector<pair<Pos, int>> currs{{Pos(0, 0), 0}};
int cycles = 0;
while(!currs.empty()) {
cycles++;
vector<pair<Pos, int>> n_currs;
for(auto curr: currs) {
if(curr.second == s.size()) {
return cycles - 1;
}
for(auto nei: neis) {
Pos n_pos = curr.first;
while(in_bounds(n_pos.x, c) && in_bounds(n_pos.y, r) && keys[n_pos.x][n_pos.y] == keys[curr.first.x][curr.first.y]) {
// if(max_match[n_pos.x][n_pos.y] < curr.second) {
// n_currs.emplace_back(n_pos, curr.second);
// max_match[n_pos.x][n_pos.y] = curr.second;
// }
n_pos = n_pos + nei;
}
if(in_bounds(n_pos.x, c) && in_bounds(n_pos.y, r) && max_match[n_pos.x][n_pos.y] < curr.second) {
n_currs.emplace_back(n_pos, curr.second);
max_match[n_pos.x][n_pos.y] = curr.second;
}
}
if(keys[curr.first.x][curr.first.y] == s[curr.second]) {
n_currs.emplace_back(curr.first, curr.second + 1);
max_match[curr.first.x][curr.first.y] = curr.second + 1;
}
}
swap(currs, n_currs);
}
return -1;
}
int main() {
while(!cin.eof()) {
int c = calc();
if(c != -1)
cout << c << endl;
}
}
funciona cuando lo runeo tipo ./prog < file.in, pero como no se el nombre de la file no puedo hacer que la lea automaticamente
¡Hola!
Te edité el post usando el elemento [details=“Summary”] , que se cierra con un [/details], y es la forma de hacer “spoilers” (se ponen esos cosos en su propia línea, con el texto a esconder entre medio).
En los problemas de Live Archive, se lee desde cin, y se escribe a cout. Es decir que eso lo estás haciendo bien, el problema debe estar en otro lado. En un rato trato de mirarlo y ver si encuentro algún problema, si no lo marcó otro antes.
Buenas, en el problema del Tesoro me da 97/100 puntos, no encuentro el error. Me podrían ayudar porfavor?
Es mi primera vez haciendo Bfs así que les pido paciencia si hice cualquier cosa 
.
Se me ocurrió crear F vectores (en realidad use map pero para que se entienda mejor) de [M][N] y entonces guardas cada lugar que vas visitando dependiendo de las flechas gastadas, por ejemplo, si gasto 4 flechas y llegó a la casilla (4, 2) guardaría en F[4] que en la casilla [4][2] ya fue visitada.
Entonces utilizando esto le aplicas Bfs, vas recorriendo todos los estados posibles y apenas llegas a la casilla del tesoro terminas el programa haciendo un backtracking del recorrido.
#include<bits/stdc++.h>
#define forn(i, n) for(int i = 0; i < int(n); i++)
using namespace std;
vector< vector < map<int, pair<int, int> > > > bfsMapParents;
vector< vector< map<int, int> > > bfsMapSteps;
vector< vector<char> > maze;
queue< pair<int, pair<int, int> > > actLevel;
deque< pair<int, int> > shortestPath;
int M, N, F, shortestLength = -1;
ifstream fin("tesoro.in");
ofstream fout("tesoro.out");
deque< pair<int, int> > backtracking(int i, int i2, int tempLevel){
deque< pair<int, int> > path;
map<int, pair<int, int> >::iterator it;
while(i != 0 || i2 != 0){
path.push_front({i, i2});
it = bfsMapParents[i][i2].find(tempLevel);
if(maze[i][i2] == 'W')
tempLevel--;
i = it->second.first, i2 = it->second.second;
//cout << "back" << endl;
}
path.push_front({0, 0});
return path;
}
bool wasVisited(int i, int i2, int level){
map<int, int>::iterator it = bfsMapSteps[i][i2].find(level);
if(it != bfsMapSteps[i][i2].end())
return true;
else
return false;
}
void showAnswer(){
fout << shortestLength << endl;
while(!shortestPath.empty()){
fout << "(" << shortestPath.front().first << ", " << shortestPath.front().second << ")" << endl;
shortestPath.pop_front();
}
}
void moveTo(int i, int i2, pair<int, int> parent, int level, int steps){
if((wasVisited(i, i2, level) && maze[i][i2] != 'W')|| (maze[i][i2] == 'W' && wasVisited(i , i2, level+1)) || maze[i][i2] == 'P')
return;
if(maze[i][i2] == 'W' && level+1 <= F){
bfsMapSteps[i][i2].insert({level+1, steps + 1});
bfsMapParents[i][i2].insert({level+1, parent});
actLevel.push({level+1, {i, i2}});
}else if(maze[i][i2] == 'V'){
bfsMapSteps[i][i2].insert({level, steps + 1});
bfsMapParents[i][i2].insert({level, parent});
actLevel.push({level, {i, i2}});
}else if(maze[i][i2] == 'T'){
bfsMapSteps[i][i2].insert({level, steps + 1});
bfsMapParents[i][i2].insert({level, parent});
if(shortestLength == -1 || (steps + 1 < shortestLength)){
shortestLength = steps + 1;
shortestPath = backtracking(i, i2, level);
showAnswer();
exit(0);
}
}
}
void printMap(){
forn(level, F)
forn(i, M){
forn(i2, N)
cout << bfsMapSteps[i][i2].find(level)->second << " ";
cout << endl;
}
cout << endl << "--------------------------------------" << endl;
}
int main(){
fin >> M >> N >> F;
maze = vector< vector<char> >(M, vector<char>(N));
bfsMapParents = vector< vector < map<int, pair<int, int> > > >(M, vector < map<int, pair<int, int> > >(N));
bfsMapSteps = vector< vector< map<int, int> > >(M, vector< map<int, int> >(N));
forn(i, M){
string fila;
fin >> fila;
forn(i2, N)
maze[i][i2] = fila[i2];
}
moveTo(0, 0, {0, 0}, 0, 0);
while(!actLevel.empty()){
int i = actLevel.front().second.first, i2 = actLevel.front().second.second, level = actLevel.front().first;
actLevel.pop();
// Steps taken
map<int, int>::iterator it = bfsMapSteps[i][i2].find(level);
if(i > 0)
moveTo(i-1, i2, {i, i2}, level, it->second);
if(i < M - 1)
moveTo(i+1, i2, {i, i2}, level, it->second);
if(i2 > 0)
moveTo(i, i2 - 1, {i, i2}, level, it->second);
if(i2 < N - 1)
moveTo(i, i2+1, {i, i2}, level, it->second);
//cout << "act" << endl;
}
fout << "imposible" << endl;
return 0;
}
Hola Michael, estuve viendo tu código. El único problema que tiene tu código, que son esos 3 puntos faltantes, es el tiempo que tarda.
Como vos bien dijiste, podías haber usado vector en vez de map. Esa pequeña sutileza hace que tu código, cuando M, N y F son “grandes” (cercanos a la cota), tarde demasiado. Buscar los iteradores, e insertar {clave, valor} en un mapa se hacen en tiempo logarítmico con respecto a la cantidad de claves que tiene. Una manera de probar este caso es por ejemplo:
forn(i, M){
string fila;
//cin >> fila;
forn(i2, N){
if(i==M-1 || i2==0){
maze[i][i2] = 'V';
}else{
maze[i][i2] = 'W';
}
}
}
maze[M-1][N-1]='T';
Con M=N=F=120.
Fijate que eso lo que hace es un camino bajando y a la derecha para llegar fácil, y tu código ahí tarda 6 segundos.
Siempre está bueno probar “casos borde”: eso es cuando lo números son muy chiquitos, muy grandes. Acá casos bordes podrían ser cuando en la entrada hay un fantasma y tenés o no tenés flechas, cuando en la entrada está el tesoro, y esas cosas “particulares”. Tu código pasa todo eso porque es correcto, el único problema es el tiempo.
Entonces lo único que tendrías que hacer es modificar todos los usos de map por vector, y por ejemplo en wasVisited podés hacer por ejemplo if(bfsMapSteps[i][i2][level]!=-1), inicializando todos los elementos de bfsMapSteps en -1, ya que de ninguna manera podés llegar con un camino en -1 pasos.
A pesar de esto, la verdad es que me gustó tu código, está bien modularizado, la idea de hacer la función moveTo está buena 
Saludos!
EDIT: Vamos a seguir conversando el código por privado, quedan algunas sugerencias pendientes. Aviso para que el resto no crea que el código así como está está perfecto.
Hola @reedef , acabo de ver tu código. No lo miré en detalle, pero de por sí me parecía turbio el cin.eof , si bien en algunos lugares lo vi, creo que no es una buena práctica usarlo. Lo que podés hacer es
int R, C
while(cin>>R>>C){
int c = calc(R, C);
....
}
Y configurar la función “calc” para que reciba los parámetros.
Le cambié eso solo y me dio Accepted!
Así que prácticamente tu algoritmo está bien, y si bien es una cagada que pase esto, hay que tener cuidado con el método de entrada/salida que elegimos usar.
En general se usa lo que te digo del while. A veces la entrada termina con dos ceros ponele y se puede hacer while(cin>>R>>C && (R!=0 || C!=0) ), o si ambos son positivos te ahorrás uno y sólo ponés R!=0 por ejemplo.
En fin, felicitaciones adelantadas por el problema
A seguir resolviendo envíos y practicando!
Ahí edité las respuestas de Michael y Cherny para que tengan el código “bonito y con Syntax Highlighting”. Para eso hay que escribir rodear el código entre “triples comillas para atrás”, y sale todo lindo y legible 
Se pueden ver más tips de formato en el foro acá.
@sebach ya identificó la cuestión, que tenía que ver con el uso del método eof, y la forma de “leer hasta que se termine el archivo” que recomendó es la más práctica y la que recomendamos para todo.
Dicho esto, solo para ampliar, comento “por qué eof no andaba”. eof solo se prende cuando ya se llegó al fin de archivo. Ahora bien, si lo único que falta leer es por ejemplo “el enter del final” o cualquier cosa de ese estilo, no se llegó al eof todavía, y entonces va a dar false. Pero para nosotros, “sí se llegó”, porque ya no hay nada útil que leer. Esto lo tenés resuelto en tu código de una manera “adhoc”, que no debería ser necesaria, que es poner ese valor especial -1, y de esta manera “procesar un caso extra fruta al final de todo”, con la esperanza de que todo salga bien y produzca el -1, y una vez afuera de calc(), poner un if especial para saltear ese -1. Esto tiene dos desventajas: una es que “es feo” hacer todo este mecanismo artesanal: querríamos de una “saber si de verdad quedan cosas útiles por leer todavía, y ni procesar un caso más si no quedan”. Esto se hace de la forma que sugirió Seba. Pero el otro problema es que cuando calc() se manda a calcular este caso extra, está usando los datos que surgen de usar cin pero sobre un archivo que ya se terminó. En ese caso, “no sabemos qué datos se leen”, y queda cualquier fruta. En otras palabras, el código como está es inválido porque se manda a procesar ese caso extra del final, y ahí se podría leer cualquier cosa. En particular, algo que haga al programa fallar, o quizás hasta producir un número que no sea -1 y se muestre, dando WA. En casos chiquitos parece andar bien en mi compu con mi compilador, pero no hay nada que garantice que esto siga siendo así en casos grandes, en otras compus, con otros compiladores.
Por otro lado, cuando compilo tu código me da todos estos warnings:
g++ -D_GLIBCXX_DEBUG -std=c++11 -DACMTUYO -O2 -g -Wconversion -Wshadow -Wall -Wextra -o "testingSotoLalala" "testingSotoLalala.cpp" -lgmp -pthread
(in directory: /home/santo/Documents/C++)
testingSotoLalala.cpp: In constructor ‘Pos::Pos(int, int)’:
testingSotoLalala.cpp:7:20: warning: declaration of ‘y’ shadows a member of ‘Pos’ [-Wshadow]
Pos(int x, int y): x(x), y(y) {}
^
testingSotoLalala.cpp:6:7: note: shadowed declaration is here
int y;
^
testingSotoLalala.cpp:7:20: warning: declaration of ‘x’ shadows a member of ‘Pos’ [-Wshadow]
Pos(int x, int y): x(x), y(y) {}
^
testingSotoLalala.cpp:5:7: note: shadowed declaration is here
int x;
^
testingSotoLalala.cpp: In function ‘int calc()’:
testingSotoLalala.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(curr.second == s.size()) {
^
Compilation finished successfully.
Quizás a vos no te salen porque no los tenés activados. Como ayudan a detectar muchos errores de programación que es muy bueno que el compilador avise antes que sufrir una hora buscando errores, recomiendo súper fuertemente activar los warnings. Acá se comentan las opciones del compilador para activarlas. ¡¡Cualquier duda sobre cómo hacerlo, consultar!!
En este caso las cosas que te marca no son bugs, pero cosas muy parecidas podrían serlo. “Silenciar” estas falsas alarmas es muy simple:
curr.second == s.size()
se transforma en
curr.second == int(s.size())
Siempre es buena idea pasar a entero con signo los .size(), por ejemplo si usaras .size()-1 sobre algo vacío sin el casteo, tendrías el programa funcionaría probablemente mal. Activando los warnings, el compilador avisa todos los lugares donde puede faltar uno de estos casteos.
El otro warning es en Pos, que indica que los parámetros x e y “esconden” o “tapan” a las variables x e y el Pos mismo. Lo mejor es ponerles un nombre diferente para evitar eso, como por ejemplo newX y newY:
struct Pos {
int x;
int y;
Pos(int newX, int newY): x(newX), y(newY) {}
};
Esto me parece además que es mejor, porque el otro patrón de ponerles el mismo nombre tiene cierto peligro: si por ejemplo hacemos:
struct Pos {
int x;
int y;
Pos(int x, int t): x(x), y(y) {}
};
Que tiene un sencillo error de tipeo de poner una t en lugar de una y (que están al lado en el teclado Qwerty), esto compilaría, pero estaría mal (porque la y se está inicializando consigo misma, en lugar de con el t) así que el programa fallaría, y encontrar este bug probablemente sería difícil de ver, porque la lógica está perfecta pero es un error sutil en un caracter mal escrito. Compilando con los warnings activados, por en este caso avisaría dos cosas que hacen que descubramos esto rápido: Que el parámetro t no se usa, y que la la variable y se está inicializando consigo misma.
Moraleja: ACTIVAR LOS WARNINGS. Salvan vidas.
Puede ser que esté caído el link de Keyboarding?
Probé logueado y tampoco, me lleva al home.
A mi me funciona. Si te sigue sin funcionar avisame por privado.
Ahora sí, habrá sido mantenimiento o algo
El problema 3, el último ejemplo:
6 4
AXYB
BBBB
KLMB
OPQB
DEFB
GHI*
AB
La salida es
7
No debería ser 10?
En un lugar dice
Each key is made up of one or more grid squares, which will always form a connected region.
Me parece que esto es lo que no estoy entendiendo, no lo puedo solucionar ni a mano
Acá está mi código que funciona bien con el primer input (el de 30):
#include <iostream>
#include <unordered_map>
#include <vector>
#include <fstream>
#define INF 10000000
using namespace std;
struct Tecla {
Tecla(int x, int y, int best = INF) : x(x), y(y), best(best) {}
int x, y;
int best;
int operator-(const Tecla& other) {
return abs(x - other.x) + abs(y - other.y);
}
};
typedef std::vector<Tecla> KeyPositions;
typedef std::unordered_map<char, KeyPositions> KeysMap;
void move(int index, KeysMap& keys, const string& str){
KeyPositions& keysBefore = keys[str[index - 1]];
KeyPositions& keysNow = keys[str[index]];
//cout << str[index - 1] << " => "<< str[index] << endl;
for(auto& key : keysNow) {
key.best = INF;
for(auto& key_b : keysBefore) {
key.best = min(key.best, key_b.best + (key - key_b) + 1);
//cout << key_b.best << ", "<< key.best << endl;
}
}
if(str.length() > index + 1)
move(index + 1, keys, str);
}
int main() {
ifstream cin("input.in");
KeysMap keys;
int r, c;
while(cin >> r >> c){
keys.clear();
keys['\0'].emplace_back(0, 0, 0);
char ch;
for(int i = 0; i < r; i++){
for(int j = 0; j < c; j++) {
cin >> ch;
keys[ch].emplace_back(i, j);
}
}
string str;
cin >> str;
str = '\0' + str + "*";
/*
for(auto& kv : keys){
cout << kv.first << ": ";
for(auto& v : kv.second){
cout << "(" << v.x << ", " << v.y << ") ";
}
cout << endl;
}
*/
move(1, keys, str);
int shortest = INF;
for(auto& key : keys[str.back()])
shortest = min(shortest, key.best);
cout << shortest << endl;
//cout << "================================" << endl;
}
return 0;
}
Hola, fijate que cuando hay muchas letras iguales agrupadas en fila o en “grid squares” como dice el enunciado que sería en forma rectangular, las toma todas como una sóla tecla.
Claro, lo que ya dijeron: el teclado no es una “grilla”, hay teclas “grandes”, como la barra espaciadora, que ocupan “muchas casillas de 1x1”, pero pese a ello son una única tecla.