Tävlingsprogrammering/Uppgifter/Skyddsrum

Skyddsrum

Manhattan är under bombhot. Gamla skyddsrum utspridda på olika ställen i stadsdelen rustas upp och förbereds för användning. När flyglarmen ljuder är det viktigt att alla vet var närmaste skyddsrum är så de kan ta sig dit snabbt. Ett litet problem är dock att vid vissa korsningar är det inte självklart vilket skyddsrum man ska ta sig till; det finns flera att välja på dit avståndet är lika långt (och inget annat är närmare). Skriv ett program som, givet storleken på stadsdelen och var skyddsrummen ligger, bestämmer antalet sådana platser.

Som bekant består gatunätet i Manhattan av horisontella och vertikala gator. För enkelhetens skull betraktar vi stadsdelen som ett rektangulärt rutnät av gator (se figuren ovan). Man kan aldrig snedda utan bara gå på gatorna. Avståndet mellan två korsningar med koordinater (h1, v1) och (h2, v2) blir därför abs(h1 − h2) + abs(v1 − v2). Skyddsrummen är alltid placerade i en korsning.

Indata

Första raden i filen newyork.dat innehåller två heltal H och V (1 ≤ H, V ≤ 30, 000), an- talet horisontella respektive vertikala gator. Gatorna numreras från 1 till H respektive 1 till V . Därefter följer en rad med talet N (1 ≤ N ≤ 10), antalet skyddsrum. Sedan följer N rader med två heltal vardera, h och v (1 ≤ h ≤ H, 1 ≤ v ≤ V ), som anger vid vilka korsningar skyddsrummen ligger. Ingen korsning kommer ha mer än ett skyddsrum.

Utdata

Skriv ut ett tal: antalet korsningar där fler än ett skyddsrum är det närmaste.

Exempel

Svar

Lösning

Den uppenbara lösningen är att loopa igenom samtliga rutor (närmare en miljard för de största indata) och för varje ruta kolla avstånd till de olika skyddsrummen. I slutändan kommer nästan 10 miljarder avstånd av beräknas, vilket är aningen för långsamt.

För att komma vidare kan man inse att det finns stora områden inom rutnätet där samma skyddsrum är det närmaste. Man kan därför fundera på om det går att bearbeta större områden än bara en ruta åt gången.

För att vara mer exakta, anta att vi har en rektangel (x1,y1)-(x2,y2) och vill kolla vilka skyddsrum som är närmast rutorna inne i rektangeln (inklusive kanterna). Vi börjar med att kolla vilka skyddsrum som är närmaste de fyra hörnen, (x1,y1), (x1,y2), (x2,y1), (x2,y2). Om det är exakt samma skyddsrum (antingen ett enda eller samma uppsättning) som är närmaste alla fyra hörn, gäller detta även för alla rutor inom rektangeln! Det är rätt lätt att bevisa genom att anta att om det skulle finns någon ruta inom rektangeln som har ett skyddsrum som är närmare, så kan inte alla fyra hörnen ha samma uppsättning närmaste skyddsrum.

Så, om vi hittar rektanglar med denna egenskap behöver vi inte loopa igenom alla rutor däri. En divide-and-conquer lösning ligger då nära till hands. Om vi har en rektangel där de fyra hörnen inte har samma uppsättning närmaste skyddsrum, delar vi upp den rektangeln i fyra lika stora delar och löser de delarna rekursivt. Hela lösningen kan bli så här:

 #include <iostream>
 
 using namespace std;
 
 const int MAX = 10;
 
 int n;
 int sx[MAX], sy[MAX];
 int bitCount[1<<MAX];
 
 int getMask(int x, int y)
 {
   int bestDist, bestMask = 0;
   for(int i=0;i<n;i++) {
     int dist = abs(x-sx[i]) + abs(y-sy[i]);
     if (i==0 || dist < bestDist) {
       bestMask = 0;
       bestDist = dist;
     }
     if (dist == bestDist)
       bestMask |= (1<<i);      
   }
   return bestMask;
 }
 
 int count(int x1, int y1, int x2, int y2)
 {
   if (x1>x2 || y1>y2) 
     return 0;
   if (x1==x2 && y1==y2)
     return bitCount[getMask(x1,y1)] > 1;
   
   int m1 = getMask(x1, y1), m2 = getMask(x1, y2), m3 = getMask(x2, y1), m4 = getMask(x2, y2);
 
   if (m1==m2 && m1==m3 && m1==m4)
     return bitCount[m1] > 1 ? (x2-x1+1)*(y2-y1+1) : 0;
   
   int mx = (x1+x2)/2, my = (y1+y2)/2;
   return count(x1,y1,mx,my) + count(mx+1,y1,x2,my) + count(x1,my+1,mx,y2) + count(mx+1,my+1,x2,y2);
 }
 
 int main()
 {
   int xsize, ysize;
   cin >> xsize >> ysize >> n;
   for(int i=0;i<n;i++)
     cin >> sx[i] >> sy[i];
     
   bitCount[0] = 0;
   for(int i=1;i<(1<<n);i++)
     bitCount[i] = bitCount[i>>1] + (i&1);
     
   cout << count(1,1,xsize,ysize) << endl;
   
   return 0;
 }

Liknande lösning i Java, som förmodligen inte är lika effektiv, men förhoppningsvis lite enklare att förstå för den som inte är en hejare på bitshiftningar och bitoperatorer.

import java.util.*;
import java.io.*;
import java.awt.*;

public class Skyddsrum
{
	//Antal korsningar med lika långt till två skyddsrum eller fler.
	static int antal = 0;

	//Skyddsrummens positioner.
	static Point [] skydd;

	//Avgör avståndet mellan punkten (x,y) och p.
	public static int distance(int x, int y, Point p)
	{
		return Math.abs(x-p.x) + Math.abs(y-p.y);
	}

	//Retunerar de skyddsrum som ligger närmast punkten (x,y).
	//Kan vara en, kan vara flera.
	public static Point[] get(int x, int y)
	{
		//Hittills kortaste avståndet.
		int min = distance(x, y, skydd[0]);

		//Sparar indexen för de närmsta skyddsrummen.
		LinkedList <Integer> index = new LinkedList <Integer> ();
		index.add(0);

		//Hittar de närmsta skyddsrummen.
		for(int i = 1; i<skydd.length; i++)
		{
			int dist = distance(x, y, skydd[i]);

			if(dist<min)
			{
				min = dist;
				index.clear();
				index.add(i);
			}
			else if(dist==min)
			{
				index.add(i);
			}
		}

		//Array där vi sparar de närmsta skyddsrummen.
		Point [] closest = new Point [index.size()];

		//Läser in vilka de var.
		int i = 0;
		for(Integer in : index)
		{
			closest[i] = skydd[in];
			i++;
		}

		//Retunerar dem.
		return closest;
	}

	//Vår rekursiva metod som löser problemet.
	//(x,y) det övre vänstra hörnet.
	//w = bredd. h = höjd.
	public static void rek(int x, int y, int w, int h)
	{
		//Närmaste skyddsrum för det övre vänstra hörnet.
		Point [] c1 = get(x, y);

		//Övre högra hörnet.
		Point [] c2 = get(x+w-1, y);

		//Nedre vänstra och nedre högra.
		Point [] c3 = null, c4 = null;

		//Om de två första har samma.
		boolean same = Arrays.equals(c1, c2);

		//Då är det nödvändigt att kolla tredje.
		if(same)
		{
			c3 = get(x, y-h+1);

			//Om tredje också har samma.
			same = Arrays.equals(c2, c3);
		}

		//Samma som ovan.
		if(same)
		{
			c4 = get(x+w-1, y-h+1);
			same = Arrays.equals(c3, c4);
		}

		//Om alla är lika.
		if(same)
		{
			//Och har flera som är lika nära.
			//Då ökar vi på antalet.
			if(c1.length>1) antal += w*h;

			//Var det bara en som var lika, så är vi ändå klara.
		}
		else //Annars, delar upp rektangeln i fyra delar.
		{
			//If-satserna är viktiga för att vi inte ska i slutskedena
			//få samma punkt i flera rektanglar. Dvs vi vill inte ha
			//rektanglar med höjd eller bredd 0.

			if(w>1 && h>1) rek(x, y, w/2, h/2);
			if(h>1) rek(x+w/2, y, w-w/2, h/2);
			if(w>1) rek(x, y-h/2, w/2, h-h/2);
			rek(x+w/2, y-h/2, w-w/2, h-h/2);
		}
	}

	//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 newyork.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\newyork.dat.4"));

		//Bredden.
		int H = scan.nextInt();

		//Höjden
		int V = scan.nextInt();

		//Antalet skyddsrum.
		int N = scan.nextInt();

		skydd = new Point [N];

		//Läser in skyddsrummen.
		for(int i = 0; i<N; i++)
		{
			skydd[i] = new Point(scan.nextInt(), scan.nextInt());
		}

		//Finner svaret.
		rek(1, V, H, V);

		//Skriver ut svaret.
		System.out.println("Antal korsningar: " + antal);
	}
}