Tävlingsprogrammering/Uppgifter/Kvarteret
Kvarteret
Visar kvarteret
FIGUR 1. Körningsexempel.
Figuren visar ett kvarter med totalt 25 hus uppförda på en kvadratisk tomt med 5 × 5 hus. Husen har höjderna 10, 20, 30, 40 och 50 våningar, och måste vara placerade på ett sådant sätt att det i varje rad och kolumn finns exakt ett hus av varje höjd. Pilarna och talen anger hur många hus man kan se i den raden eller den kolumnen om man tittar i pilens riktning. Lägre hus skyms ju av högre!
Skriv ett program som med hjälp av den givna informationen bestämmer och skriver ut de 25 husens höjd i antal våningar som en kvadrat med 5 rader och 5 kolumner.
Indata är filen kvarter.dat, som innehåller 20 tal på en rad, separerade med blanksteg, antalet hus man kan se i en viss riktning, eller talet 0 som innebär att information i den riktningen saknas. Talen ges medurs med början högst upp till vänster.
Körningsexempel:
Filen kvarter.dat med innehållet: 0 1 0 3 0 2 0 0 0 0 0 2 0 0 0 1 3 4 5 2 ska ge svaret: 40 50 10 20 30 10 20 30 40 50 20 30 40 50 10 30 40 50 10 20 50 10 20 30 40
Lösning
redigeraLösning i Java. Den här uppgiften är inte särskilt svår, men dock lite omständlig. En enkel lösning (vilken jag har valt) är att helt enkelt testa sig fram, vi testar att bygga ett hus av viss höjd på första tomten, sedan testar vi att bygga ett hus av annan höjd på nästa tomt, osv. Till en början kan man kanske tro att det totalt finns 5!^5 tillstånd, men detta stämmer inte eftersom villkoret max en byggnad per höjd också ska gälla för kolumner, vilket gör att totala antalet tillstånd snarare blir 5!*4*4!*3*3*3!*2*2*2*2!*1! = 288*5!*4!*3!*2!*1! = ca 10 miljoner = ingenting. Sedan begränsas vi ju också av informationen om hur många hus vi ska se från olika riktningar, vilket ger ännu färre tillstånd. Så svårigheten i den här uppgiften ligger alltså inte i att göra en effektiv lösning, utan att göra en korrekt lösning.
I denna lösning så börjar vi på tomten längst upp till vänster och sedan går vi åt höger tills raden är slut då vi börjar på en ny rad, osv tills vi har byggt hus i hela kvarteret som uppfyller villkoren. Innan vi testar att bygga ett hus på en viss tomt, så kollar vi givetvis om vi får bygga huset där (dvs att det inte redan finns hus av samma höjd i samma kolumn och rad). Sedan när vi har byggt klart en rad, så kollar vi om den uppfyller villkoren för den raden (om inte så backtrackar vi). Slutligen när vi har kommit till sista raden och bygger hus, så kollar vi också att villkoren för kolumnerna uppfylls. När vi till slut har kommit till slutet av kvarteret, så vet vi att husen som nu står byggda i kvarteret är svaret (eftersom vi kontinuerligt kontrollerat rader och kolumner), så då kan vi avbryta och skriva ut svaret.
(Givetvis kan man göra en hel del optimeringar i koden, men det är onödigt eftersom programmet ändå går så snabbt som det gör.)
import java.util.*;
import java.io.*;
public class Kvarteret
{
//Vårt kvarter.
static int [][] kvarter = new int [5][5];
//Sparar villkoren för respektive rad och kolumn i kvarteret.
static int [][] conditions;
//Testar alla möjliga giltiga kombinationer tills vi har funnit ett svar.
//(x, y) koordinaten där vi testar att placera ett hus.
public static boolean rek(int x, int y)
{
//Vi är färdiga med en rad.
if(x==5)
{
//Kollar om raden uppfyller villkoren.
if(!checkRow(y)) return false;
//Börjar på en ny rad.
x = 0;
y++;
}
//Vi är klara och om vi är klara, så har vi svaret.
if(y==5)
{
//Talar om för alla hus att de står rätt.
return true;
}
//Testar att placera alla möjliga hus på denna position.
for(int i = 10; i<51; i+=10)
{
//Får vi placera huset här så gör vi det.
//Annars går vi vidare och testar med nästa hus.
if(isOK(i, x, y))
{
kvarter[y][x] = i;
}
else continue;
//När vi placerar hus på sista raden måste vi också
//kolla att vi uppfyller villkoren för kolumnerna.
if(y==4)
{
//Om villkoret inte uppfylls får vi testa ett annat hus.
if(!checkCol(x)) continue;
}
//Placerar ett hus på nästa position.
//Om det visar sig att det huset står rätt, så står vårt
//hus också rätt och vi avbryter och talar om för föregående
//hus att han också står rätt.
if(rek(x+1, y)) return true;
}
//Avmarkerar positionen.
//(Behövs vid backtrackingen när ett nytt hus på en tidigare position ska prövas.)
kvarter[y][x] = 0;
//Det gick inte att placera ett hus på denna position utifrån hur
//de tidigare husen placerats. Talar om det för dem.
return false;
}
//Kollar om en viss rad uppfyller villkoren.
public static boolean checkRow(int y)
{
//Hämtar höger och vänster villkoren för raden.
int limitLeft = conditions[1][y+5];
int limitRight = conditions[0][y+5];
int nr = 0; //Hur många hus vi ser.
int max = 0; //Högsta huset vi ser.
//0 = det kan vara vad fan som helst, onödigt att kolla.
if(limitLeft!=0)
{
//Kollar hur många hus vi ser från vänster.
for(int i = 0; i<5; i++)
{
if(kvarter[y][i]>max)
{
max = kvarter[y][i];
nr++;
}
if(nr>limitLeft) return false;
}
//Ser vi inte så många hus som villkoret dikterar, så är det fel.
if(nr!=limitLeft) return false;
}
nr = 0; max = 0;
//Kollar från höger.
if(limitRight!=0)
{
for(int i = 4; i>=0; i--)
{
if(kvarter[y][i]>max)
{
max = kvarter[y][i];
nr++;
}
if(nr>limitRight) return false;
}
if(nr!=limitRight) return false;
}
//Vi har klarat testerna.
return true;
}
//Kollar om en viss kolumn uppfyller villkoren.
public static boolean checkCol(int x)
{
//Hämtar upp och ned villkoren för denna kolumn.
int limitUp = conditions[0][x];
int limitDown = conditions[1][x];
int nr = 0; //Hur många hus vi ser.
int max = 0; //Högsta huset vi ser.
//0 = det kan vara vad fan som helst, onödigt att kolla.
if(limitUp!=0)
{
//Kollar hur många hus vi ser uppifrån.
for(int i = 0; i<5; i++)
{
if(kvarter[i][x]>max)
{
max = kvarter[i][x];
nr++;
}
if(nr>limitUp) return false;
}
//Ser vi inte så många hus som villkoret dikterar, så är det fel.
if(nr!=limitUp) return false;
}
nr = 0; max = 0;
//Kollar nedifrån.
if(limitDown!=0)
{
for(int i = 4; i>=0; i--)
{
if(kvarter[i][x]>max)
{
max = kvarter[i][x];
nr++;
}
if(nr>limitDown) return false;
}
if(nr!=limitDown) return false;
}
//Vi har klarat testerna.
return true;
}
//Kollar om det är OK att placera ett visst hus på en viss position.
//Dvs huruvida om huset redan existerar i raden eller kolumnen.
public static boolean isOK(int house, int x, int y)
{
//Kollar så att huset inte finns i raden.
for(int i = 0; i<5; i++)
{
if(kvarter[y][i]==house) return false;
}
//Kollar så att huset inte finns i kolumnen.
for(int i = 0; i<5; i++)
{
if(kvarter[i][x]==house) return false;
}
//Vi har klarat testerna.
return true;
}
//Orka fånga exceptions. Vi är lata och säkra på vår sak.
public static void main(String [] klein) throws FileNotFoundException
{
//Vi ska läsa av filen kvarter.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\kvarter.dat"));
//Index [0][0...4] villkoren uppifrån för kolumnerna i kvarteret.
//Index [0][5...9] villkoren från höger för raderna i kvarteret.
//Index [1][0...4] villkoren nedifrån för kolumnerna i kvarteret.
//Index [1][5...9] villkoren från vänster för raderna i kvarteret.
conditions = new int [2][10];
//Läser in villkoren för kolumnerna uppifrån och raderna från höger.
for(int i = 0; i<10; i++)
{
conditions[0][i] = scan.nextInt();
}
//Läser in villkoren för kolumnerna nedifrån.
for(int i = 0; i<5; i++)
{
conditions[1][4-i] = scan.nextInt();
}
//Läser in villkoren för raderna från vänster.
for(int i = 0; i<5; i++)
{
conditions[1][9-i] = scan.nextInt();
}
//Finner svaret.
rek(0, 0);
//Skriver ut husen i kvarteret.
for(int i = 0; i<5; i++)
{
for(int j = 0; j<5; j++)
{
System.out.print(kvarter[i][j] + " ");
}
System.out.println();
}
}
}