Hola! Hace tiempo vengo intentando resolver el problema Laberinto ajedrecístico, del Certamen Selectivo de 2009 (http://juez.oia.unsam.edu.ar/#/task/ajedrez/statement), pero se me va de tiempo en los casos más grandes y no veo como optimizarlo más.
Mi pensamiento del problema es el siguiente:
Por cada casilla del tablero, tengo múltiples movimientos. Consideramos que me encuentro en la \color{red}{\text{x}}:
- Si uso el caballo, puedo ir todas las casillas a las que puedo llegar formando una L. Es decir, todas las combinaciones en las cuales me desplace 2 casillas en una coordenada, y 1 en la otra.
- Si uso el alfil, serían todas en diagonal. Es decir, aquellas donde la cantida que varío en una coordenada es igual a lo que varío en la otra.
- Si uso la torre, es en línea recta. Es decir, lo que varío en una coordenada debe ser 0.
Con los movimientos de caballo no tengo problema, porque llego a lugares fijos. Mientras, con la torre y el alfil puedo ir a todos los posibles casilleros en llínea o en diagonal respectivamente, hasta llegar a un obstáculo. Y yo no puedo suponer que iré hasta el obstáculo, porque puede que un movimiento a medio camino luego me lleve a otros movimientos que resultarán en el coste mínimo. Entonces no me queda otra que fijarme todos los posibles caminos. Si yo considero la grilla como un grafo en el cual cada celda es un nodo, puedo hacer un Dijkstra, que debería obtener el camino más corto.
Si formo el grafo nodo por nodo dados los posibles movimientos en cada uno, se va de tiempo claramente. Mi primer approach era ir metiendo en el priority_queue todas los posibles lugares con los que puedo llegar con cada arista, pero justamente por lo que dije, en los casos más grandes se va de tiempo.
Así que la segunda opción que probé es solo ver con las celdas cercanas a las que puedo ir por cada celda. Es decir, moverme de a pasos lo más chicos posibles, y sumo costo (y cantidad de jugadas) cuando de una casilla a otra me muevo distinto de lo que hice para llegar a la anterior. Entonces así doy prioridad a los caminos de menor costo, y como yo quiero justamente el valor del mínimo costo, apenas llego a destino puedo cortar y tener el resultado. Y por supuesto al probar las posibilidades de cada casilla, me aseguro de no irme fuera del tablero o a algún obstáculo, que los marco en la entrada en un array bidimensional de booleanos.
Esta solución me da 80 ptos. Más allá un caso de prueba que da WA (que probablemente es un caso borde que no tengo en cuenta, caso 2), me da TLE en los casos 16, 17, y 18. Llegué a esto después de unas optimizaciones controlando la cantidad de elementos que llevo en el priority_queue, y no veo ninguna optimización más que pueda hacer.
Dejo mi código:
Código
#include <bits/stdc++.h>
#define forn(i,n) for(int i = 0; i < int(n); i++)
#define forsn(i,s,n) for(int i = int(s); i < int(n); i++)
#define dforn(i,n) for (int i = int(n)-1; i >= 0; i--)
#define dforsn(i,s,n) for(int i = int(n)-1; i >= int(s); i--)
#define all(c) (c).begin(),(c).end()
#define fst first
#define snd second
#define FAST_IO ios::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 1e3+10;
const int MAXTM = 16; // máximos tipos de movimientos
const int INF = 1e9+2;
const int X[] = {0,1,0,-1, 2,-2,2,-2,1,-1,1,-1, 1,-1,1,-1}; // X (Torre || Caballo || Alfil)
const int Y[] = {1,0,-1,0, 1,1,-1,-1,2,2,-2,-2, 1,-1,-1,1}; // Y (Torre || Caballo || Alfil)
bool tablero[MAXN][MAXN];
int D[MAXN][MAXN][MAXTM]; // distancia dijkstra
int play[MAXN][MAXN][MAXTM]; // jugadas por casillero
int N;
struct nodo {
int x,y,p; // vertice, puntos penalización
int jugadas;
int cnt, mov; // cantidad consec, tipo, mov específico
bool operator< (const nodo &o) const{
return o.p < p;
}
};
bool valid (int &x, int &y) {
if (x < 0 or y < 0) return false;
if (x >= N or y >= N) return false;
return true;
}
int typ (int &i) {
if (i > 3)
if (i > 11)
return 2;
else return 1;
else return 3;
}
void bfsDijkstra(int stX, int stY) {
priority_queue<nodo> Q;
forn (i,MAXTM) D[0][0][i] = 0;
Q.push({stX,stY,0,0,0,-1});
while (not Q.empty()) {
auto e = Q.top(); Q.pop();
if (e.x == N-1 and e.y == N-1) return;
forn (i,MAXTM) {
int tipo = typ(i), tipo2 = typ(e.mov);
bool toAdd = (e.mov != i or tipo == 1); // ¿NUEVA JUGADA?
if (tipo2 == tipo and e.cnt+toAdd > 2) continue; // no más de dos mov. consec
int tX = e.x+X[i], tY = e.y+Y[i]; // hacia donde voy
if (!valid(tX,tY)) continue; // que no me pase del tablero
if (tablero[tY][tX]) continue; // tampoco me tope con un obstáculo
//cout << e.x << ' ' << e.y << ' ' << e.mov << ' ' << i << ' ' << tipo2 << ' ' << tipo << ' ' << e.cnt+toAdd << ' ' << D[tY][tX][i] << ' ' << e.p + (toAdd ? tipo : 0) << ' ' << tX << ' ' << tY << endl;
if (D[tY][tX][i] == -1 or D[tY][tX][i] > e.p + (toAdd ? tipo : 0)) { // ¿acorto haciendo así?
D[tY][tX][i] = e.p + (toAdd ? tipo : 0); // actualizo
play[tY][tX][i] = e.jugadas+toAdd;
//fprintf(stdout,"(%d,%d) -> (%d %d) con %d pen y %d jug\n",e.x,e.y,tX,tY,D[tY][tX][i],play[tY][tX][i]);
Q.push({tX,tY,D[tY][tX][i],play[tY][tX][i],(tipo2 == tipo ? e.cnt+toAdd : 1),i}); // nuevo camino
}
}
}
}
int main() {
freopen("ajedrez.in","r",stdin);
freopen("ajedrez.out","w",stdout);
memset(D,-1,sizeof(D));
int c;
scanf("%d %d",&N,&c);
forn(i,c) { // marco en el tablero los obstáculos
int y1,x1,y2,x2;
scanf("%d %d %d %d",&y1,&x1,&y2,&x2);
x1--; y1--; x2--; y2--;
if (abs(x1-x2) == abs(y1-y2)) { // diagonal;
while (x1 != x2) {
tablero[y1][x1] = true;
if (x2 >= x1) x1++; else x1--;
if (y2 >= y1) y1++; else y1--;
}
tablero[y1][x1] = true;
}
else {
if (x1 >= x2 and y1 >= y2) {swap(x1,x2); swap(y1,y2);} // coords más altas en x2 e y2
if (x1 == x2) { // vertical
while (y1 <= y2) {
tablero[y1][x1] = true;
y1++;
}
}
else { // horizontal
while (x1 <= x2) {
tablero[y1][x1] = true;
x1++;
}
}
}
}
/*forn (i,N) {
forn(j,N) cout << tablero[i][j];
cout << endl;
}*/
bfsDijkstra(0,0);
int a = INF, b = INF;
forn (i,MAXTM)
if (D[N-1][N-1][i] < a and D[N-1][N-1][i] != -1) {
a = D[N-1][N-1][i];
b = play[N-1][N-1][i];
}
printf("%d %d",b,a);
return 0;
}
Espero alguien sepa de alguna optimización o mejora de la idea que pueda aplicar. Gracias!
), pero creo que verlo como distancias es más intuitivo. Con eso me saqué un poco de encima el problema de marcar más de la cuenta cada nodo, considerando como estados ahora sí (me recordó un poco a DP), condiciones de las cuales “tengo la mismas posibilidades de resultados”: 