Buscando un tema para un concurso de programación
1. Juego de ajedrez:
Este es un juego con una sola pieza de ajedrez. El tablero de ajedrez se divide en cuadrados con N filas y M columnas, y una determinada posición está marcada como punto final T. En cualquier posición, la pieza de ajedrez puede moverse un cuadrado en cuatro direcciones: izquierda, derecha, arriba y abajo, y la distancia de movimiento se registra como 1.
Hay algunas casillas especiales en el tablero de ajedrez: aviones. Cada avión tiene una distancia de vuelo d. Una vez que la pieza de ajedrez lo alcanza, puede continuar "volando" d casillas en la misma dirección y el movimiento. la distancia sigue siendo 1. Por ejemplo, si la pieza de ajedrez está en la posición (2, 8), el avión está en la posición (2, 7) y la distancia de vuelo es 5, entonces la pieza de ajedrez se mueve un cuadrado hacia la izquierda y alcanzará directamente la posición ( 2, 2) con una distancia de movimiento de 1. Si el punto de vuelo queda fuera del tablero, sólo podrá detenerse en el borde. Por ejemplo, si la distancia de vuelo del avión anterior es 10, entonces la posición final de la pieza de ajedrez es (2, 1).
Además, si el punto de aterrizaje después del vuelo sigue siendo el avión, continuará volando hasta el destino, y el punto intermedio no afectará a la pieza de ajedrez actual y, por supuesto, no contará ningún movimiento. distancia. Por ejemplo, si la pieza de ajedrez está en (2,8), el avión está en (2,7), (2,5) y la distancia de vuelo es 5, y la pieza de ajedrez se mueve un espacio hacia la izquierda, entonces el avión en (2,5) no tendrá ningún efecto y la distancia de movimiento seguirá siendo 1.
Tu tarea es programar y calcular la distancia de movimiento más corta para que la pieza de ajedrez llegue al punto final.
Entrada:
La entrada puede tener múltiples casos de prueba. La primera línea de cada caso de prueba son dos números enteros N y M (3 <= N, M <= 100), que representan el número de filas y columnas en el tablero de ajedrez. Seguido de un número entero K, que indica el número de aeronaves. Cada una de las siguientes K líneas tiene 3 números enteros positivos x, y y d, que representan respectivamente la posición de la aeronave (x, y) (2 <= x <= N-1, 2 <= y <= M-1) y distancia de vuelo d. La primera línea de las dos últimas líneas es la posición inicial S de la pieza de ajedrez y la segunda línea es la posición final T. Puede suponer que los datos siempre son válidos, S y T, y la posición de la aeronave son diferentes entre sí. Ingrese 0 0 para indicar el final.
Salida:
Cada caso de prueba genera una línea, que es la distancia más corta hasta el punto final. Si no se puede alcanzar, se emite "Imposible".
2. Número mínimo de monedas:
(Me resulta particularmente problemático ingresar esta pregunta y espero que se pueda proporcionar un mejor método de entrada)
Esta es una pregunta antigua y clásica. En general, hay muchas formas de recuperar una determinada cantidad de dinero utilizando una cantidad determinada de monedas. Por ejemplo: dados 6 tipos de monedas con valores nominales de 2, 5, 10, 20, 50 y 100, para recolectar 15 yuanes, puede usar 5 2 yuanes, 1 5 yuanes o 3 5 yuanes o 1 5 yuanes, 10 yuanes cada uno, etc. Obviamente, se necesitan al menos 2 monedas para formar 15 yuanes.
Tu tarea es, dadas varias denominaciones de monedas diferentes, programar para calcular el número mínimo de monedas necesarias para formar una cantidad determinada de dinero.
Entrada:
La entrada puede tener múltiples casos de prueba. La primera línea de cada caso de prueba es el valor del dinero a recaudar, M (1 <= M <= 2000, entero. En la siguiente línea, el primer número entero K (1 <= K <= 10) representa el. número de monedas, seguido de K diferentes valores nominales de monedas Ki (1 <= Ki <= 1000). Finaliza cuando se ingresa M=0.
Salida:
Cada caso de prueba genera una línea, que es el número mínimo de monedas necesarias para que el dinero tenga un valor M. Si la recaudación de dinero falla, se emite "Imposible". Puedes asumir que la cantidad de cada tipo de monedas a recolectar es infinita.
Entrada de muestra:
15
6 2 5 10 20 50 100
1
1 2
0
Salida de muestra:
2
Mejor respuesta imposible a la primera pregunta, BFS típico para encontrar el camino más corto
2 p>
#include
#define MAXN 105
usando el espacio de nombres std
const int dir[4] [2]={ {0,1},{0,-1},{1,0},{-1,0}};
int m,n
int cabeza,cola;
int cola[MAXN*MAXN][3]; MAXN][MAXN] ;
int tx,ty;
int main()
{
mientras (cin>>n >>m && n >0)
{
int i,j,k
memset(mapa,0,tamañode(mapa)); /p>
cin>>k;
mientras (k--)
{
cin>>i>>j
i --;
j--;
cin>>mapa[i][j]
}
memset(hash ,true,sizeof(hash));
cin>>cola[0][0]>>cola[0][1]; 0][0] --;
cola[0][1]--;
cola[0][2]=0; [cola[0] [0]][cola[0][1]]=falso;
cabeza=0
cola=1; cin>>tx> >ty;
tx--;
ty--;
mientras (cabeza { for (k=0;k<4;k++) { i=cola[cabeza][ 0]+dir[ k][0]; j=cola[head][1]+dir[k][1]; mientras (i>=0 && i { i+=mapa[i][j]*dir[ k][0] ; j+=map[i][j]*dir[k][1] if (i<0 || i>=n | | j<0 | | j>=m) { si (i<0) i=0 si (i>=n) i=n-1 si (j<0) j=0 si (j>=m) j=m; -1; romper; } } si (i>=0 && i if (hash[i][j]) { cola[tail][0]=i; > cola[cola][1]=j cola[cola][2]=cola[cabeza][2]+1 hash[i] [j]=false; if (i==tx && j==ty) cout< tail++; p> p> } } cabeza++; } if (hash[tx][ty]) cout< <"impossible"< } return 0; } La segunda pregunta es un DP típico Utilice f[i][j] para representar el número mínimo de monedas necesarias para generar una cantidad total de j dinero utilizando los primeros i valores de moneda Ecuación de transición de estado f[i ][j] =min{f[i-1][j](i>0),f[i][j-Ki]+1(j>=Ki), infinito} #include #define MAXM 2010 #definme MAXK 15 usando el espacio de nombres std int m,k; int m,k; p> int K[MAXK] int f[MAXK][MAXM]; int main() { mientras (cin>>m && m>0) { int i ,j; cin>>k; para (i=1;i<=k;i++) cin>>K[i]; memset(f,-1,tamañode(f)); f[0][0]=0 for (i=1;i<=k;i++) for (j=0;j<=m;j++ ) { int min min=-1; if (f[i-1][j]! =-1 && (min==-1 || f[i-1][j] if (j>=K [i] && f[i][j-K[i]]!=-1 && (min==-1 || f[i] [j-K[i]]+1 f[i][j]=min if (f[k][m]= =-1) cout<<"imposible"< else cout< } devuelve 0;