Me he puesto a resolver algunos problemas planteados del code jam donde siempre nos encontramos dos trabas la primera entender “bien” el problema a resolver que adicionalmente no esta en nuestro idioma y segundo pensar en un algoritmo que nos permita desarrollarlo.
En función a ello, me encontré este problema que puede ver desde el portal del codejam el cual me tomo un buen rato desarrollarlo, primero por que me costo entenderlo, tuve que leerlo varias veces y luego pensar en el código, finalmente lo logré y me di cuenta que se puede mejorar agregando unos llamados a funciones pero ya igual funciona, así que lo dejaré así. Una traducción al problema planteado, podría ser:
Imagine que se encuentra a fuera de un laberinto perfecto. Un laberinto es perfecto si y solo si cumple las siguientes condiciones:
- Es rectangular con filas R y columnas C.
- Solo existen dos aperturas en el, la entrada y la salida.
- Existe solo un camino que dará la solución al laberinto.
Usted decide resolver el laberinto perfecto usando el algoritmo “Cruzar siempre a la izquierda” lo que significa que se debe cruzar a la izquierda en cada oportunidad posible. Si te encuentras en un camino sin salida debe cruzar dos veces a la derecha (180 grados) y seguir. (Si puedes cruzar a la izquierda sin tocar el muro entonces habrás resuelto el laberinto). Cuando finalmente terminas el laberinto te provoca hacerlo de nuevo, pero esta vez en sentido contrario de la salida a la entrada.
El camino que tomas a través del laberinto es descrito con tres letras: “W” significa caminar hacia adelante hasta la siguiente habitación, “L” significa doblar a la izquierda (cruzar 90 grados) , y la ultima letra “R” nos indica que se debe doblar a la derecha (cruzar 90 grados). Se inicia desde afuera del laberinto por el lado de la puerta de la entrada en frente del laberinto. Se termina al dar un paso por la salida del laberinto. Por ejemplo, si la entrada se encuentra en el norte y la salida en el oeste, el camino sería WRWWLWWLWWLWLWRRWRWWWRWWRWLW:
Si la entrada y la salida son invertidas, de forma que se inicio en la pared oeste y se salió por la norte el camino a recorrer sería WWRRWLWLWWLWWLWWRWWRWWLW. Teniendo en cuenta las dos rutas ( entrada a salida y salida a entrada ) el código debe arrojar una descripción del laberinto.
Entrada:
La primera línea de la entrada contiene el numero de casos N. Seguido de los N casos para probar. Cada caso contiene una línea con el siguiente formato:
entrada_a_salida salida_a_entrada
Todos los caminos tienen como mínimo dos letras, y solo posee “W”, “L” y “R” , y siempre inicia y termina con “W”.
Salida.
En cada caso de prueba, la línea debe contener “Case #x:” por si misma. Las siguientes R líneas dan una descripción de R y C del laberinto. Por cada línea deben haber C caracteres, que representan las direcciones posibles para caminar en la sala del laberinto. Teniendo en cuenta la siguiente leyenda:
| Carácter | Puede caminar al norte? | Puede caminar al sur? | Puede caminar al oeste? | Puede caminar al este? |
| 1 | Sí | No | No | No |
| 2 | No | Sí | No | No |
| 3 | Sí | Sí | No | No |
| 4 | No | No | Sí | No |
| 5 | Sí | No | Sí | No |
| 6 | No | Sí | Sí | No |
| 7 | Sí | Sí | Sí | No |
| 8 | No | No | No | Sí |
| 9 | Sí | No | No | Sí |
| a | No | Sí | No | Sí |
| b | Sí | Sí | No | Sí |
| c | No | No | Sí | Sí |
| d | Sí | No | Sí | Sí |
| e | No | Sí | Sí | Sí |
| f | Sí | Sí | Sí | Sí |
Limites
1 ≤ N ≤ 100.
Data corta
2 ≤ longitud(entrada_a_salida) ≤ 100,
2 ≤ longitud(salida_a_entrada) ≤ 100.
Data larga
2 ≤ longitud(entrada_a_salida) ≤ 10000,
2 ≤ longitud(salida_a_entrada) ≤ 10000.
Ejemplo
Entrada
2 WRWWLWWLWWLWLWRRWRWWWRWWRWLW WWRRWLWLWWLWWLWWRWWRWWLW
WW WW
Salida
Case #1:
ac5
386
9c7
e43
9c5
Case #2:
3
Finalmente, en el portal pueden descargan muchas soluciones que se encuentran publicadas, pero no están comentadas, yo medio comente mi código en c++ y aquí se los dejo:
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <list>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <complex>
#include <cstdio>
#include <cassert>
#include <cmath>
#if defined (__GNUC__) && (__GNUC__ <= 2)
#include <hash_map>
#include <hash_set>
#else
#include <ext/hash_map>
#include <ext/hash_set>
using namespace __gnu_cxx;
#endif
using namespace std;
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define rep(i,n) FOR(i,0,(n)-1)
#define repd(i,n) for(int i=(n)-1;i>=0;i--)
#define sz size()
template<class T> inline int size(const T& c) { return c.sz; }
#define FORA(i,c) rep(i,size(c))
#define itype(c) __typeof((c).begin())
#define FORE(e,c) for(itype(c) e=(c).begin();e!=(c).end();e++)
#define pb push_back
#define X first
#define Y second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define REVERSE(x) reverse(all(x))
#define CLEAR(x,c) memset(x,c,sizeof(x))
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
LL s2i(string s) { istringstream i(s); LL x; i>>x; return x; }
template<class T> string i2s(T x) { ostringstream o; o << x; return o.str(); }
#define pi acos(-1.)
#define eps 1e-7
#define inf 1000000000
#define maxn 1100
#define maxp 1100000
#define ll long long
char a[10001], b[10001]; // a: entrance to exit. b: exit to entrance
int maze[10001][10001]; // matriz para el laberinto.
int lmaze = 10000; // longitud maxima del laberinto
int r,c; // filas y columnas
int la,lb;
int d=2 ; // direccion 1 norte, 2 sur, 3 oeste, 4 este
int main()
{
int i,j,k,m,n,p,q,N;
FILE *fp=fopen("input.in", "r"), *ofp=fopen("output.out", "w");
fscanf(fp,"%d",&N);
rep(k,N) {
fscanf(fp, "%s %s", a,b);
r=0,c=0;
la=strlen(a);
lb=strlen(b);
// limpiando el laberinto
rep(i,lmaze) rep(j,lmaze) maze[i][j]=15;
d=2; // direccion incial hacia el sur
// comenzando a calcular las paredes, en sentido entrada salida
int i=0;
int j=0; // primer elemento de la matriz del laberinto
// se comienza a crear el laberinto desde la entrada a la salida
rep(m,la) {
switch (a[m]) {
case 'W':
if (m==0) {
maze[i][j]-=1; // se abre la entrada
r+=1;
c+=1;
}
else {
// encontrando el ultimo punto del camino...
if (m==la-1) {
switch (d) {
case 1:
maze[i][j]=maze[i][j]&(~1);
d=2;
break;
case 2:
maze[i][j]=maze[i][j]&(~2);
d=1;
break;
case 3:
maze[i][j]=maze[i][j]&(~4);
d=4;
break;
case 4:
maze[i][j]=maze[i][j]&(~8);
d=3;
break;
}
break;
}
// determinando la nueva posicion y tamano del maze
switch (d) {
case 1:
i-=1; // subiendo hacia el norte
maze[i][j]=maze[i][j]&(~2);
maze[i+1][j]=maze[i+1][j]&(~1);
break;
case 2:
i+=1; // baja hacia el sur
if (r==i) r+=1; // el laberinto es mas grande
maze[i][j]=maze[i][j]&(~1);
maze[i-1][j]=maze[i-1][j]&(~2);
break;
case 3:
// hacia el oeste
// este caso es cuando es mas grande y se desplaza todo el laberinto
if (j==0) {
c+=1; // nuevo tamano
// se empieza desplazar todos los campos...
repd(p,r) {
repd(q,c) {
switch (q) {
case 0:
if (p==i) maze[p][q]=7; // solo abierta la entrada del este
else maze[p][q]=15; // se llenan los demas
break;
case 1:
//maze[p][q]=maze[p][q-1]-4; // abre el muro y copia paredes
maze[p][q]=maze[p][q-1];
/*if (i+1==q)
maze[p][q]=maze[p][q]&(~4); */
break;
default:
maze[p][q]=maze[p][q-1]; // copia el valor
break;
} // switch (q)
}
}
} //if (i==-1)
else {
j-=1;
maze[i][j]=maze[i][j]&(~8);
maze[i][j+1]=maze[i][j+1]&(~4);
}
break;
case 4:
j+=1; // hacia el este
if (j==c) c+=1;
// determinando paredes
maze[i][j]=maze[i][j]&(~4);
maze[i][j-1]=maze[i][j-1]&(~8);
break;
} //switch (d)
} //else
break;
case 'L':
switch (d) {
case 1:
d=3; // gira del norte al oeste
break;
case 3:
d=2; // gira del oeste al sur
break;
case 2:
d=4; // gira del sur al este
break;
case 4:
d=1; // gira del este al norte
break;
} //switch (d)
break;
case 'R':
switch (d) {
case 1:
d=4; // del norte al este
break;
case 4:
d=2; // del este al sur
break;
case 2:
d=3; // del sur al oeste
break;
case 3:
d=1; // del oeste al norte
break;
} //switch (d)
break;
} //switch (a[m])
} //rep(m,la)
// Creando el camino de la salida a la entrada
rep(m,lb) {
switch (b[m]) {
case 'W':
if (m==lb-1) break; // ya se tiene el camino completo
if (m==0) {
maze[i][j]=maze[i][j]; // en el mismo punto de la salida
}
else {
// determinando la nueva posicion y tamano del maze
switch (d) {
case 1:
i-=1; // subiendo hacia el norte
maze[i][j]=maze[i][j]&(~2);
maze[i+1][j]=maze[i+1][j]&(~1);
break;
case 2:
i+=1; // baja hacia el sur
if (r==i) r+=1; // el laberinto es mas grande
maze[i][j]=maze[i][j]&(~1);
maze[i-1][j]=maze[i-1][j]&(~2);
break;
case 3:
// hacia el oeste
// este caso es cuando es mas grande y se desplaza todo el laberinto
if (j==0) {
c+=1; // nuevo tamano
// se empieza desplazar todos los campos...
repd(p,r) {
repd(q,c) {
switch (q) {
case 0:
if (p==i) maze[p][q]=7; // solo abierta la entrada del este
else maze[p][q]=15; // se llenan los demas
break;
case 1:
//maze[p][q]=maze[p][q-1]-4; // abre el muro y copia paredes
maze[p][q]=maze[p][q-1];
/*if (i+1==q)
maze[p][q]=maze[p][q]&(~4); */
break;
default:
maze[p][q]=maze[p][q-1]; // copia el valor
break;
} // switch (q)
}
}
} //if (i==-1)
else {
j-=1;
maze[i][j]=maze[i][j]&(~8);
maze[i][j+1]=maze[i][j+1]&(~4);
}
break;
case 4:
j+=1; // hacia el este
if (j==c) c+=1;
// determinando paredes
maze[i][j]=maze[i][j]&(~4);
maze[i][j-1]=maze[i][j-1]&(~8);
break;
} //switch (d)
} //else
break;
case 'L':
switch (d) {
case 1:
d=3; // gira del norte al oeste
break;
case 3:
d=2; // gira del oeste al sur
break;
case 2:
d=4; // gira del sur al este
break;
case 4:
d=1; // gira del este al norte
break;
} //switch (d)
break;
case 'R':
switch (d) {
case 1:
d=4; // del norte al este
break;
case 4:
d=2; // del este al sur
break;
case 2:
d=3; // del sur al oeste
break;
case 3:
d=1; // del oeste al norte
break;
} //switch (d)
break;
} //switch (a[m])
} //rep(m,la)
fprintf(ofp, "Case #%d:\n",k+1);
rep(i,r){
rep(j,c) {
switch (15-maze[i][j]) {
case 1:
fprintf(ofp, "1");
break;
case 2:
fprintf(ofp, "2");
break;
case 3:
fprintf(ofp, "3");
break;
case 4:
fprintf(ofp, "4");
break;
case 5:
fprintf(ofp, "5");
break;
case 6:
fprintf(ofp, "6");
break;
case 7:
fprintf(ofp, "7");
break;
case 8:
fprintf(ofp, "8");
break;
case 9:
fprintf(ofp, "9");
break;
case 10:
fprintf(ofp, "a");
break;
case 11:
fprintf(ofp, "b");
break;
case 12:
fprintf(ofp, "c");
break;
case 13:
fprintf(ofp, "d");
break;
case 14:
fprintf(ofp, "e");
break;
case 15:
fprintf(ofp, "f");
break;
}
if (j==c-1) fprintf(ofp, "\n");
}
}
}
}
0 comentarios:
Publicar un comentario en la entrada