10426 - Knights' Nightmare

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 10426 - Knights' Nightmare

Post by phoenixxx1 »

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

Post by phoenixxx1 »

Here with syntax coloring:

http://pastebin.com/ramjEvJ3

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

Re: 10426 - Knights' Nightmare

Post by phoenixxx1 »

help

Post Reply

Return to “Volume 104 (10400-10499)”