Tävlingsprogrammering/Uppgifter/Kretskortet

Kretskortet

Du har fått till uppgift att designa en del av ett kretskort. Du måste sammanbinda den övre delen av kortet med den undre delen genom att dra så många ledningar som möjligt. Det finns dock redan ett antal skruvhål på kortet som inte kan flyttas och måste undvikas. Skriv ett program som tar en beskrivning av skruvhålens position på kretskortet och beräknar det maximala antalet ledningar som kan dras. De lediga positionerna i den översta raden motsvarar möjliga startpunkter för ledningar, och de lediga positionerna i den nedersta raden motsvarar möjliga slutpunkter.

Ledningarna måste vara korta; med det menas att de varken kan gå i sidled eller bakåt på kortet. De börjar på den översta raden och förflyttar sig i varje steg antingen rakt ned, ned och ett steg åt vänster, eller ned och ett steg åt höger. Två dataledningar får inte korsa eller beröra varandra.

På första raden i filen kretskort.dat står två heltal: höjden (2 ≤ H ≤ 100) och bredden (2 ≤ B ≤ 100) på kretskortet, separerade med blanksteg. Därefter följer H rader som vardera innehåller en sträng med B tecken. Varje tecken beskriver en position på kretskortet och är antingen ’.’ (tom plats) eller ’o’ (skruvhål). Programmet ska skriva ut det maximala antalet ledningar som kan dras från översta till nedersta raden så att skruvhålen undviks.

Exempel: Filen kretskort.dat med innehållet

5 8 
.o.ooo.. 
o....... 
.....ooo 
........ 
.o.oo... 

ska ge svaret

Antal ledningar: 3 

Lösning

Lösningsexempel i C:

#include <stdio.h>

int H,W;
char map[100][101];

int MLX(int r, int last) {     //r=raden, last=kolumnen i föregående rad
  int p;
  if(r==H) return 1;   //Ledningen färdigdragen
  for(p=0;p<W;p++) if(((last==-1) || (p-last)*(p-last)<=1) && map[r][p]=='.') {    //Loopa över angränsande kolumner med tom position.
      map[r][p]='X';   //Markera positionen som besökt (antingen dras ledningen här eller så går det inte att dra ledning här)
      if(MLX(r+1,p)) return 1;    //Om en möjlig ledningsdragning hittas, returnera hela vägen tillbaka till main
    }
  return 0;  //Hittade ingen möjlig ledning från denna position.
}

int main(){
  int i,n;
  FILE *fil=fopen("kretskort.dat", "rt");
  fscanf(fil, "%d %d", &H, &W);
  for(i=0;i<H;i++) fscanf(fil, "%s", map[i]);
  n=0;
  while(MLX(0,-1)) n++;    //Försök dra ledningar så länge det går
  printf("Antal ledningar: %d\n", n);
  return 0;
}

Här nedan följer ett lösningsexempel i Java. I exemplet utnyttjas följande insikter.

• Om vi kan dra en ledning från en punkt (till mål) så ska vi dra den.
• Om vi kan dra flera så ska vi alltid försöka välja den som viker av mest åt vänster i ett tidigt skede.
• För om den första ledningen (som är den närmast vänsterkanten) viker av maximalt åt vänster, så bör vi försöka få nästa ledning att vika av maximalt åt vänster för att spara plats åt andra ledningar.
• Om vi från en punkt inte lyckades dra ledningen i mål, så kommer inga andra ledningar heller att lyckas dra sin ledning i mål från den punkten. (D.v.s. vi ska markera de punkter på kretskortet som vi försökt dra ledning ifrån, så att vi får dynamisk programmering på köpet i lösningen.)

Observera också att vi lösningen utnyttjar det faktum att om den första satsen i ett logiskt uttryck innehållandes && misslyckas, så exekveras inte de övriga satserna.

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

public class Kretskortet
{
	//Hur vårt kretskort ser ut.
	static char [][] kretskort;

	//Kretskortets bredd.
	static int width;

	//Kretskortets höjd.
	static int height;

	//Talar om huruvida det går att dra en ledning från en viss punkt
	// på kretskortet ner till slutraden.
	public static boolean makeLine(int x, int y)
	{
		//Vi drar ledningen genom den här punkten.
		kretskort[y][x] = 'x';

		//Om vi kommit till sista raden har vi lyckats.
		if(y==height-1) return true;

		//Testar först om det går att dra en ledning från punkten under till vänster.
		//Om inte så testar vi om det går att dra ifrån punkten rakt under.
		//Om inte det går så testar vi att dra ifrån punkten under till höger.
		if(isOK(x-1, y+1) && makeLine(x-1, y+1)) return true;
		else if(isOK(x, y+1) && makeLine(x, y+1)) return true;
		else if(isOK(x+1, y+1) && makeLine(x+1, y+1)) return true;

		//Av bara ren vana kan man råka inkludera denna rad, men det är ju faktiskt
		// onödigt och väldigt dumt, så gör det inte!
		/*** kretskort[y][x] = '.'; ***/

		//Om ingen dragning lyckades så gick det inte att komma fram från denna punkt.
		return false;
	}

	//Talar om huruvida det är tillåtet att dra en ledning genom den angivna punkten.
	public static boolean isOK(int x, int y)
	{
		//Om vi är utanför gränserna på kortet, så är det definitivt otillåtet.
		if(x<0 || x>=width) return false;
		else if(y>=height) return false;

		//Om det är en ledig punkt så är den tillåten, annars inte.
		return (kretskort[y][x]=='.');
	}

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

		height = scan.nextInt();
		width = scan.nextInt();

		//Skapar kretskortet.
		kretskort = new char [height][width];

		//Läser in kretskortet.
		for(int i = 0; i<height; i++)
		{
			String rad = scan.next();

			kretskort[i] = rad.toCharArray();
		}

		//Hur många ledningar vi kan dra.
		int antal = 0;

		//Går igenom översta raden och försöker dra ledningar.
		for(int i = 0; i<width; i++)
		{
			//Dock försöker vi bara dra ifrån tillåtna punkter.
			if(kretskort[0][i]=='.')
			{
				//Om det gick att dra en ledning från den här
				// punkten så ökar vi antalet vi kan dra.
				if(makeLine(i, 0)) antal++;
			}
		}

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