Tävlingsprogrammering/Uppgifter/Wordfeud
Wordfeud
Wordfeud är ett scrabble/alfapet-liknande spel där man ska lägga ut bokstavsbrickor på en rutig spelplan så att det bildas ord. Orden kan läggas antingen från vänster till höger eller uppifrån och ned. Varje bokstav ger en viss poäng. Dessutom finns ett antal specialrutor på spelplanen, som kan vara av fyra typer:
- DL (double letter): bokstavspoängen för en bricka på denna ruta dubbleras
- TL (triple letter): bokstavspoängen för en bricka på denna ruta tredubblas
- DW (double word): poängen för hela ordet dubbleras om rutan täcks
- TW (triple word): poängen för hela ordet tredubblas om rutan täcks
När man räknar ut poängen för ett ord börjar man med att summera bokstavspoängen, med eventuell multiplikation på varje bokstav. När summan är uträknad multipliceras den med eventuella ordmultiplikatorer. Observera att om ordet ligger på flera DW- eller TW-rutor kan poängen multipliceras flera gånger.
I den här uppgiften tänker vi oss en tom 10x10 spelplan där raderna och kolumnerna är numrerade enligt figuren. Skriv ett program som, givet specialrutornas placering på spelplanen och det ord du tänker lägga ut, beräknar den högsta poäng du kan få om du får lägga ordet var du vill (men hela ordet inom spelplanen).
Spelplanen i exemplet med specialrutorna utmärkta. De skuggade områdena visar tre exempel på placering av “ordet” 56141. Den lodräta placeringen ger 2*(2*5+6+1+2*4+1)=52 poäng, den vågräta på rad 3 ger 51 poäng och den vågräta på rad 5 ger 33 poäng.
Programmet ska fråga efter antalet specialrutor (högst 10 stycken) och sedan läsa in deras koordinater och typ enligt dialogen nedan. Både raden och kolumnen ligger i intervallet 1 till 10 och typen är alltid DL, DW, TL eller TW. Slutligen ska programmet fråga efter ordet som ska läggas. För enkelhets skull har varje bokstav redan ersatts med sitt poängvärde, en siffra mellan 0 och 8. Ordet kan ha upp till 7 bokstäver.
Körningsexempel 1
Antal specialrutor ? 5 Specialruta 1, rad ? 2 Specialruta 1, kolumn ? 7 Specialruta 1, typ ? DL Specialruta 2, rad ? 5 Specialruta 2, kolumn ? 5 Specialruta 2, typ ? TL Specialruta 3, rad ? 6 Specialruta 3, kolumn ? 7 Specialruta 3, typ ? DW Specialruta 4, rad ? 5 Specialruta 4, kolumn ? 7 Specialruta 4, typ ? DL Specialruta 5, rad ? 3 Specialruta 5, kolumn ? 6 Specialruta 5, typ ? TW Ord ? 56141 Maxpoäng: 52
Körningsexempel 2
4 1 9 DW 1 10 DL 2 9 TW 2 10 TL 174 Maxpoäng: 72
Körningsexempel 3
9 1 1 DL 1 4 DW 3 1 TW 3 4 TL 2 3 TL 2 8 TW 9 3 DW 9 8 DW 9 2 DL 2152652 Maxpoäng: 100
Lösning[redigera]
Det finns ju högst 2*10*10 ställen att lägga ordet så vi hinner loopa igenom alla och räkna ut poängen för varje plats.
Exempellösning i C:
#include <stdio.h>
#include <string.h>
int MAX(int p, int q) { return p>q?p:q; }
int main() {
char type[3],word[8];
int map[10][10],ns,i,j,k,l,n,wm,lm,sum,best,r,c;
scanf("%d", &ns);
for(i=0;i<10;i++) for(j=0;j<10;j++) map[i][j]=1;
for(i=0;i<ns;i++) {
scanf("%d %d %s", &r,&c,type); r--;c--;
if(type[0]=='D') k=2;
else k=3;
map[r][c]=(type[1]=='W') ? -k: k; //Lägg in specialrutorna på kartan: 1,2,3 betyder bokstavsmultiplikation, -2,-3 betyder ordmultiplikation
}
scanf("%s", word);
n=strlen(word);
best=0;
for(i=0;i<10;i++) for(j=0;j+n<=10;j++) for(l=0;l<2;l++) { //Loopa över alla möjliga placeringar och riktningar
wm=1 ;
sum=0;
for(k=0;k<n;k++) { //Loopa över bokstäverna i ordet
lm=(l==0) ? map[i][j+k] : map[j+k][i]; //Vågrätt eller lodrätt?
if(lm<0) {
wm*=(-lm); //Öka på multiplikationsfaktorn
lm=1; //Se till att rutan inte räknas som bokstavspoäng också.
}
sum+=(word[k]-'0')*lm; //Addera bokstavspoängen till summan, eventuellt multiplicerad med bokstavspoängen
}
sum*=wm; //Gör multiplikationen med multiplikationsfaktorn.
best=MAX(best,sum); //Spara bästa resultatet hittills.
}
printf("%d\n", best);
return 0;
}
En listig implementation är nyckeln till framgång i den här uppgiften. Vi subtraherar 1 från indata för kolumn samt rad, eftersom vi gillar 0-indexering.
import java.util.*;
public class WordFeud
{
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Antal specialrutor ? ");
final int N = scan.nextInt();
//0 = vanlig ruta, 1 = DL, 2 = TL, 3 = DW, 4 = TW.
int [][] board = new int [10][10];
//Läser in specialrutorna.
for(int i = 1; i<=N; i++)
{
System.out.printf("Specialruta %d, rad ? ", i);
final int rad = scan.nextInt();
System.out.printf("Specialruta %d, kolumn ? ", i);
final int kol = scan.nextInt();
System.out.printf("Specialruta %d, typ ? ", i);
final String typ = scan.next();
int t = 0;
if(typ.equals("DL")) t = 1;
else if(typ.equals("TL")) t = 2;
else if(typ.equals("DW")) t = 3;
else t = 4;
board[rad-1][kol-1] = t;
}
System.out.print("Ord ? ");
String ord = scan.next();
//Gör om Strängen till en array med motsvarande tal.
int [] v = new int [ord.length()];
for(int i = 0; i<v.length; i++) v[i] = ord.charAt(i) - '0';
int max = 0; //Max poäng.
//Vi testar att placera ut ordet på alla positioner.
for(int i = 0; i<10; i++)
for(int j = 0; j<10; j++)
{
//Poäng och produkten av alla DW samt TW.
int score = 0, mul = 1;
if(j+v.length<=10) //Om ordet får plats vågrätt
for(int k = 0; k<v.length; k++) //Beräknar bokstavpoängen för ordet.
{
score += v[k]; //Adderar poängen för bokstaven.
//Om rutan är vanlig, DL eller TL ska den räknas 0, 1, respektive 2 extra gånger.
if(board[i][j+k]<3) score += v[k]*board[i][j+k];
else mul *= board[i][j+k]-1; //Annars är det en DW eller TW.
}
score *= mul; //Multiplicerar bokstavpoängen med produkten av alla DW och TW.
//Nu har vi fått vår slutgiltiga poäng, är den bättre än tidgare bästa?
if(score>max) max = score;
score = 0; mul = 1;
if(i+v.length<=10) //Om ordet får plats lodrätt.
for(int k = 0; k<v.length; k++)
{
if(board[i+k][j]<3) score += v[k]*board[i+k][j];
else mul *= board[i+k][j]-1;
score += v[k];
}
score *= mul;
if(score>max) max = score;
}
System.out.println("Maxpoäng: " + max);
}
}