Tävlingsprogrammering/Uppgifter/Robotar

Från Wikibooks


Robotar

I datorspelet Robots ska spelaren försöka undvika ett gäng galna robotar. Det finns många robotar mot den ensamma spelaren, men deras rörelser är förutsägbara och spelaren kan utnyttja detta.

Spelet spelas på ett bräde som är RxK stort. Följande fem steg upprepas:

Spelaren flyttar ett steg i en av åtta riktningar (horisontellt, vertikalt eller diagonalt) eller står kvar. Om spelaren flyttar till en ruta där en robot står förlorar han spelet. Varje robot försöker därefter närma sig spelaren genom att flytta sig ett steg i någon av de åtta riktningarna. Roboten försöker alltså minimera värdet av abs(r1-r2) + abs(k1-k2) där (r1,k1) och (r2,k2) är spelarens och robotens position. Om någon robot hamnar på samma ruta där spelaren befinner sig förlorar spelaren spelet. Om två eller fler robotar hamnar på samma ruta exploderar dessa och alla robotar i den rutan försvinner. Givet startpositionen för spelare, robotarna och hur spelaren kommer att röra sig, beräkna hur spelet kommer att sluta. Om spelaren lyckas göra alla förflyttningar och överlever, skriv ut hur brädet ser ut efter alla förflyttningar. Om spelaren inte överlever, skriv ut antalet drag spelaren hann göra innan spelet tog slut. Indata

Den första raden innehåller två heltal, R och K (1 ≤ R ≤ 100, 1 ≤ K ≤ 100), antalet rader och kolumner som brädet har.

De följande R raderna innehåller K tecken vardera och beskriver hur brädet ser ut vid spelets början. Tecknet '.' motsvarar en tom ruta, 'R' en robot och 'I' spelaren.

Den avslutande raden innehåller en sträng på högst 100 siffror som beskriver spelarens förflyttningar. Varje förflyttning är en siffra mellan 1 och 9, där 5 betyder att spelaren står stilla. Betydelsen av övriga siffror framgår av figuren nedan:


Indata kommer vara så att spelaren aldrig försöker förflytta sig utanför brädet.

Utdata

Om spelaren lyckas göra alla drag och överlever, skriv ut hur brädet ser ut (samma format som indatat). I annat fall, skriv ut "X drag" där X är antalet drag som spelaren lyckades utföra innan han dog.

Exempel 1: Indata

4 5
I....
.....
.R.R.
.....
6

Exempel 1: Utdata

.I...
.RR..
.....
.....

Exempel 2: Indata

9 10
..........
.........R
..........
R.........
R...I.....
R.........
..........
.........R
....R.....
5558888

Exempel 2: Utdata

....I.....
....R.....
..........
..........
..........
..........
..........
..........
..........

Exempel 3: Indata

12 8
...I....
........
........
........
........
RR......
......RR
R......R
........
........
........
...R....
66445394444162

Exempel 3: Utdata

11 drag

Lösning[redigera]

Lösningen kräver bara att man kan skriva en korrekt simulering, enligt specifikationerna ovan.

#include <cstdio>
#include <cstring>
 
int R, K;
 
char plan[100][104];
char drag[101];
 
char tmp[100][104];
 
int y, x; //Spelarens aktuella position
 
static const int D[9][2] = {{1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 0}, {0, 1}, {-1, -1}, {-1, 0}, {-1, 1}};
 
int main(){
	scanf("%d%d", &R, &K);
	for(int i=0; i<R; i++){
		scanf("%s", plan[i]);
		for(int j=0; j<K; j++) if (plan[i][j] == 'I'){
			y = i, x = j;
		}
	}
	scanf("%s", drag);
	int ad = strlen(drag);
	int d;
	for(d=1; d<=ad; d++){
		int r = drag[d-1]-'1'; //Hämta ut vilken riktning man ska gå åt
		int ny = y+D[r][0], nx = x+D[r][1];
		if (plan[ny][nx] == 'R'){
			//Man krockar med en robot
			goto done;
		}
		y = ny, x = nx;
		for(int i=0; i<R; i++){
			//Det är lättare att skapa en ny plan och flytta sakerna hit istället för att jobba med en och samma plan.
			for(int j=0; j<K; j++) tmp[i][j] = '.';
			tmp[i][K] = 0;
		}
		for(int i=0; i<R; i++) for(int j=0; j<K; j++){
			if (plan[i][j] == 'R'){
				//Hitta alla robotar, och flytta dem närmare spelaren
				int dy = (i == y ? 0 : (i < y ? 1 : -1));
				int dx = (j == x ? 0 : (j < x ? 1 : -1));
				if (i+dy == y && j+dx == x)
					goto done;
				//Workaround för att veta om roboten exploderade (E), eller om den fick stå kvar
				if (tmp[i+dy][j+dx] == 'R' || tmp[i+dy][j+dx] == 'E')
					tmp[i+dy][j+dx] = 'E';
				else
					tmp[i+dy][j+dx] = 'R';
			}
		}
		for(int i=0; i<R; i++) for(int j=0; j<K; j++){
			//Ta bort alla exploderade robotar
			if (tmp[i][j] == 'E')
				tmp[i][j] = '.';
		}
		memcpy(plan, tmp, 100*104); //Kopiera över tmp till plan
	}
	plan[y][x] = 'I';
	for(int i=0; i<R; i++)
		printf("%s\n", plan[i]);
	return 0;
	done:
	printf("%d drag\n", d);
	return 0;
}