Tävlingsprogrammering/Uppgifter/Staden
Staden
FIGUR 2. Ett exempel på hur staden kan se ut. Om Boel följer den streckade linjen behöver hon bara korsa tre gator, vilket är det minsta möjliga antalet i detta fall. Observera att det aldrig kan göra någon skillnad om hon följer gatorna eller om hon sneddar.
Boel bor och arbetar i den övertrafikerade staden Tutstad. Staden har en kvadratisk form och är placerad i ett koordinatsystem så att dess sydvästra hörn, där Boel bor, ligger i punkten (0, 0) och dess nordöstra hörn, där Boel jobbar, ligger i punkten (100, 100). Längs stadens fyra ytterkanter går så avskyvärda trafikleder att man omöjligt kan passera dem till fots. Men även inne i staden är trafiken besvärlig, vilket har fått Boel att undra hur många gator hon egentligen måste korsa när hon går till fots mellan hemmet och arbetet.
Skriv ett program som, givet stadens gatunät, bestämmer det minsta antalet gator man måste korsa för att ta sig från punkten (0, 0) (innanför trafiklederna) till punkten (100, 100) (innanför trafiklederna). Indata läses från filen tutstad.dat. På första raden står ett heltal n (1 ≤ n ≤ 5000), antalet gator i staden. Därefter följer n rader med fyra heltal, x1, y1, x2 och y2, på varje rad. x1 och y1 är koordinaterna för startpunkten för en gata, medan x2 och y2 är koordinaterna för slutpunkten för gatan. För samtliga koordinater gäller att 0 ≤ x1 ≤ x2 ≤ 100 och 0 ≤ y1 ≤ y2 ≤ 100, samt att antingen x1 = x2 eller y1 = y2 (men inte både och). Varje gata är en rak sträcka mellan dessa punkter. Gatornas bredd är försumbar, så det går alltså att passera mellan två öst-västliga gator med y-koordinater y och y + 1.
Körningsexempel:
Filen tutstad.dat med innehållet:
11 20 0 20 100 0 20 60 20 60 20 60 40 0 40 60 40 70 0 70 30 80 20 100 20 80 40 100 40 80 40 80 100 40 40 40 80 40 60 100 60 40 80 100 80
ska ge svaret:
Minsta antal korsade gator: 3
Lösning[redigera]
(Finns nu i Java.) Ska infogas snart (i C förmodligen). Testar bara bilderna nu.
- De fem testfallen
-
-
-
-
-
Här nedan följer en lösning i Java. Sättet vi löser uppgiften på är det enkla att vi helt enkelt testar att gå på alla möjliga sätt och kollar vad det minsta antalet korsade gator blir. Nu kan man kanske tro att det blir väldigt många kombinationer att testa, men det blir det inte, eftersom det inte spelar roll vilken väg vi går, utan bara hur många gator vi har korsat på vägen till en viss punkt i staden.
Genom att spara hur många gator vi korsat för att nå en viss punkt, så får vi dynamisk programmering på köpet i lösningen på ett elegant sätt. Detta gör att vi förhoppningsvis inte behöver besöka en ruta (koordinat/position) i staden mer än en gång, vilket vi dock kommer att göra eftersom den optimala lösningen antagligen inte kommer att nås direkt, men fortfarande lär vi knappast besöka många fler än 10000 rutor (vilket i praktiken inte är någonting).
So far so good, men nu till problemet. Problemet är att gatorna har försumbar bredd. Detta gör att två gator kan ligga parallella och beskrivas i programmet som att de vore en tjockare gata (man kan inte gå emellan dem), men eftersom de har försumbar bredd, så ska man ju kunna gå emellan dem. Detta problem uppstår endast för testfall #5, så visst kan man vara lat och låta koden vara enkel och vacker samtidigt som man erhåller någon enstaka poäng. Men hur ska vi då lösa detta? Ja en enkel lösning är ju att helt enkelt bara förstora staden med 2. På detta sätt får vi det mellanrum vi vill ha, som gör att vi kan gå emellan två intilliggande gator. Visserligen får vi 40000 rutor som vi behöver behandla, men det är ju fortfarande ingenting.
Nu kan man kanske tro att allting är frid och fröjd, men det är det inte för nu har ett nytt problem uppstått. Tidigare hade vi 10000 rutor och som värst kan man då få ett rekursionsdjup på 10000, vilket man möjligen kanske kan klara, men 40000 metodanrop liggandes på stacken ger dig inget mer än StackOverflowError. (Detta problem uppstår främst i de lättare testfallen.) Hur löser man då detta? Jo man kan helt enkelt beräkna den bästa vandringen i staden bit för bit (steg för steg alltså). I min lösning har jag en variabel (steps) som håller reda på rekursionsdjupet och om det överstiger 1337, så avbryter vi rekursionen och sparar positionen vi var på samt hur många gator vi hade korsat (i ett objekt av en egen-skapad klass). Sedan när vi är klara med grundvandringen, så tar vi och fortsätter på de oavslutade vandringarna vi sparade undan. Observera att alla resultat som tidigare erhållits för varje koordinat (ruta) i staden fortfarande finns sparade, så att vi fortsätter på oavslutade vandringar gör inte att vi tvingas behandla fler rutor än vad vi annars hade tvingats göra (om StackOverflowError inte skulle existera), utan bara att vi beräknar vandringen genom staden pö om pö (lite i taget åt gången). Sedan kanske den bästa vandringen inte kräver mer än 1337 steg genom staden, men man kan ju inte vara nog säker och det är ju inte svårt att konstruera testfall som kräver flera steg (för Boel) att gå.
import java.util.*;
import java.io.*;
public class Staden
{
//Minsta antal gator som behöver korsas.
static int min = 5001;
//Staden i vilken vi går.
//Håller reda på det minsta antal gator vi behövt
//korsa för att nå en viss koordinat.
static int [][] chart = new int [201][201];
//Håller reda på var gatorna går.
static boolean [][] streets = new boolean [201][201];
//Sparar ouppklarade vandringar.
static LinkedList <State> unfinished = new LinkedList <State> ();
//Rekursiv metod som vandrar alla möjliga vägar genom staden.
//crossed: Antal gator vi korsat.
//x, y: Koordinaten i staden vi befinner oss på.
//steps: Antal steg vi har gått (håller reda på rekursions-djupet).
public static void walk(int crossed, int x, int y, int steps)
{
//Man får inte gå utanför staden.
if(x<0 || x>200 || y<0 || y>200) return;
//Om rekursions-djupet överstiger LEET så sparar vi undan
//vandringen (tillståndet) och avbryter.
if(steps>1337)
{
unfinished.add( new State(x, y, crossed) );
return;
}
//Nu korsar vi en gata.
if(streets[y][x])
{
crossed++;
}
//Om vi nått denna ruta på färre korsade gator än innan.
//Så uppdaterar vi koordinaten.
if(crossed<chart[y][x])
{
chart[y][x] = crossed;
}
else //Annars finns det ingen idé att fortsätta.
{
return;
}
//Lite onödigt kanske, men att gå i de "dåliga" (trafikerade)
//kvarteren är onödigt (förutsatt att vi vet om det).
if(crossed>=min) return;
//Vi har nått målet (där Boel jobbar).
if(x==200 && y==200)
{
min = crossed;
return;
}
//Går uppåt.
walk(crossed, x, y+1, steps+1);
//Går åt höger.
walk(crossed, x+1, y, steps+1);
//Går nedåt.
walk(crossed, x, y-1, steps+1);
//Går åt vänster.
walk(crossed, x-1, y, steps+1);
}
//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 tutstad.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\tutstad.dat"));
//Antalet gator.
int nr = scan.nextInt();
//Läser in gatorna.
for(int i = 0; i<nr; i++)
{
//Vi multiplicerar alla koordinater med två, eftersom vi
//förstorat staden med två.
int x1 = scan.nextInt()*2;
int y1 = scan.nextInt()*2;
int x2 = scan.nextInt()*2;
int y2 = scan.nextInt()*2;
//Markerar ut gatorna.
if(x1==x2)
{
for(int j = y1; j<=y2; j++)
{
streets[j][x1] = true;
}
}
else
{
for(int j = x1; j<=x2; j++)
{
streets[y1][j] = true;
}
}
}
//Markerar alla koordinater i staden med ett högt tal.
//(Från början har ju alla positioner värdet 0, vilket inte är så lyckat.)
for(int i = 0; i<201; i++)
{
for(int j = 0; j<201; j++)
{
chart[i][j] = 5001;
}
}
//Börjar vår vandring till jobbet.
//Vi har korsat 0 gator, börjar i koordinat (0,0) och gått 0 steg.
walk(0, 0, 0, 0);
//Avslutar (fortsätter) alla ouppklarade vandringar.
while(!unfinished.isEmpty())
{
//Plockar ut vandringen.
State st = unfinished.removeFirst();
//Fortsätter den från där den avslutades.
walk(st.crossed, st.x, st.y, 0);
}
//Skriver ut svaret.
System.out.println("Minsta antal korsade gator: " + min);
}
//Klass som beskriver ett tillstånd.
private static class State
{
public int x; //x-koordinaten.
public int y; //y-koordinaten.
public int crossed; //Antal gator som korsats.
//Konstruktor.
public State(int x, int y, int crossed)
{
this.x = x;
this.y = y;
this.crossed = crossed;
}
}
}