#include #define MAX 30 // Mez velikosti šachovnice int M, N; // Skutečná velikost šachovnice int x0, y0; // Výchozí pole int x1, y1; // Cílové pole int F[2*MAX*MAX][2]; // Fronta int r, w; // Čtecí a zápisový index fronty typedef vzdal[MAX][MAX]; vzdal K, H; // Královské a koňské vzdálenosti /* {\comment Tabulky možných tahů: Pro oba typy seznam rozdílů pro obě osy zvlášť, ukončeno kombinací $(0,0)$} */ int Kx[] = { -1, -1, -1, 0, 0, 1, 1, 1, 0 }; // Král int Ky[] = { -1, 0, 1, -1, 1, -1, 0, 1, 0 }; int Hx[] = { -2, -2, -1, -1, 1, 1, 2, 2, 0 }; // Kůň int Hy[] = { -1, 1, -2, 2, -2, 2, -1, 1, 0 }; void cesty(int vzd, vzdal K, int *dx, int *dy, int xx, int yy) { // Zkouší všechny tahy z~pozice $(xx,yy)$ int x, y; if (vzd < 0) // Běda, sem se nedostaneme! return; while (*dx || *dy) { x = xx + *dx++; y = yy + *dy++; if (x < M && y < N && K[x][y] < 0) // Sem to ještě neumíme! { F[w][0] = x; F[w][1] = y; w++; // Do fronty s~tím! K[x][y] = vzd+1; // Už umíme\dots } } } int hledej(void) // Hledání cesty { int x, y; r = 0; w = 1; F[0][0] = x0; F[0][1] = y0; // Inicializujeme frontu for(x=0; x= 0 && H[x][y] < K[x][y]); // A koněm nebo králem? dist = kun ? H[x][y] : K[x][y]; for(;;) { dist--; // A zase o 1 blíž\dots printf("(%d,%d)\n", x, y); if (x == x0 && y == y0) break; // Hotovo if (kun) dx=Hx, dy=Hy; else dx=Kx, dy=Ky; while (*dx || *dy) // Hledáme předchozí { int xx=x + *dx++, yy=y + *dy++; if (xx < M && yy < N && (kun ? K : H) [xx][yy] == dist) { x = xx, y = yy; break; } } kun = !kun; } } int main(void) { // Vstupy a výstupy :-( scanf("%d%d%d%d%d%d", &M, &N, &x0, &y0, &x1, &y1); if (hledej()) vypis(); else puts("Nenalezeno!"); return 0; }