## 10426 - Knights' Nightmare

Moderator: Board moderators

phoenixxx1
New poster
Posts: 3
Joined: Tue Dec 20, 2011 6:07 pm

### Re: 10426 - Knights' Nightmare

Hello,

posting here to avoid a duplicate.

I gave this problem a shot yesterday, I already did 3 years ago and could not solve it (get AC) so I thought I would get it over with this unfinished job... without luck!

I cannot see where my code is wrong (although I'm aware it is not the most efficient, this is another issue).

Here it is:

Code: Select all

#include <stdio.h>
#include <string.h>

int KmoveX[8] = { -1, -1,  1,  1, -2, -2,  2,  2 };
int KmoveY[8] = { -2,  2, -2,  2, -1,  1, -1,  1 };

/*
* Explore 1 échiquier
*/
void explore(char l[16][16], int r, int c)
{
int search = 0;
int go = 1;
int i, j, k, nr, nc;

while (go)
{
go = 0;
for (i = 0; i < r; i++)
for (j = 0; j < c; j++)
if (l[i][j] == search)
for (k = 0; k < 8; k++)
{
nr = i + KmoveX[k];
nc = j + KmoveY[k];
if (nr >= 0 && nr < r && nc >= 0 && nc < c && (l[nr][nc] == -1 || l[nr][nc] > search + 1))
{
l[nr][nc] = search + 1;
go = 1;
}
}
search++;
}
}

/*
* Retourne le temps minimum pour un rdv ou -1 (rdv impossible)
*/
int checkmin(char l[4][16][16], int r, int c)
{
int i, j;
int tmin, min = -1;
for (i = 0; i < r; i++)
for (j = 0; j < c; j++)
{
tmin =
(l[0][i][j] >= 0 && l[1][i][j] >= 0 && l[2][i][j] >= 0 && l[3][i][j] >= 0) ?
l[0][i][j] + l[1][i][j] + l[2][i][j] + l[3][i][j] : -1;
if (min < 0 || min > tmin)
min = tmin;
}
return min;
}

/*
void printboard(char l[16][16], int r, int c)
{
int i, j;
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
printf("%4d", l[i][j]);
printf("\n");
}
}
*/

int testcase(void)
{
int n, r, c, kr[4], kc[4], mr, mc;
int i, tmin, min = -1;	/* -1 = rdv impossible. Valeur positive = temps minimum */
char land[4][16][16];

if (fscanf(stdin, "Set#%d\n %d %d\n%d %d %d %d %d %d %d %d\n%d %d\n", &n, &r, &c, &kr[0], &kc[0], &kr[1], &kc[1], &kr[2], &kc[2], &kr[3], &kc[3], &mr, &mc) != 13)
return 0;

for (i = 0; i < 4; i++)	/* choix du bonhomme qui peut visiter le monstre */
{
/* préparation de 4 échiquiers avec points de départ dont 3 avec monstre */
int j;
memset(land, -1, 4*16*16);	/* -1 = case non visitée */
for (j = 0; j < 4; j++)
{
if (j != i)
land[j][mr-1][mc-1] = -2;	/* -2 = case du monstre */
land[j][kr[j]-1][kc[j]-1] = 0;		/* 0 = case de départ */

/* exploration de l'échiquier */
explore(land[j], r, c);

/* petit test de débugage */
/*	printboard(land[j], r, c);
printf("\n");
*/
}
/* vérification de l'existence d'un point de rendez-vous et mémorisation du temps minimum */
tmin = checkmin(land, r, c);
if (min < 0 || min > tmin) min = tmin;
}

printf("Set#%d\n", n);

if (min < 0) printf("Meeting is impossible.\n");
else printf("Minimum time required is %d minute%s.\n", min, (min == 1) ? "" : "s");

return 1;
}

int main(void)
{
do {} while (testcase());
return 0;
}

phoenixxx1
New poster
Posts: 3
Joined: Tue Dec 20, 2011 6:07 pm

### Re: 10426 - Knights' Nightmare

Here with syntax coloring:

http://pastebin.com/ramjEvJ3

phoenixxx1
New poster
Posts: 3
Joined: Tue Dec 20, 2011 6:07 pm

help