Tävlingsprogrammering/Uppgifter/Robotar
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
redigeraLö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;
}