Tävlingsprogrammering/Uppgifter/Kvadratpussel
Kvadratpussel
I figuren ser du en kvadrat (13 × 13) som är sammansatt av 11 mindre kvadrater, som också är det minsta antal “småkvadrater” man behöver för att skapa en stor kvadrat av denna storlek.
Skriv ett program som tar emot den stora kvadratens sida S , där 2 ≤ S ≤ 17, och bestämmer det minsta antal mindre kvadrater som behövs för att lägga pusslet.
Körningsexempel:
Kvadratens sida ? 13 Det behövs minst 11 kvadrater
Lösning
[redigera]Problemet kan lösas med rekursion. Man har en funktion som lägger dit en kvadrat och som sedan anropar sig själv för att lösa det nya problemet som uppstår. För att få programmet tillräckligt snabbt är det dock viktigt att man tänker på hur man lägger ut kvadraterna, så att man inte får något "hål" någonstans.
#include <stdio.h>
int s[40],map[20][20],N,min;
void MLX(int nr) {
int i,j,ii,jj;
for(i=0;i<N;i++) {
for(j=0;j<N;j++) if(!map[i][j]) break; //Hitta första tomma rutan.
if(j<N) break;
}
if(i==N) min=nr; //Ingen tom ruta - en lösning hittad
if(nr>=min-1) return; //Ingen idé att söka vidare.
for(s[nr]=N-1;s[nr]>0;s[nr]--) { //Försök lägga större kvadrater först.
if(i+s[nr]>N || j+s[nr]>N) continue;
for(ii=0;ii<s[nr];ii++) {
for(jj=0;jj<s[nr];jj++) if(map[i+ii][j+jj]) break; //Kolla överlapp
if(jj<s[nr]) break;
}
if(ii<s[nr]) continue;
for(ii=0;ii<s[nr];ii++) for(jj=0;jj<s[nr];jj++) map[i+ii][j+jj]=1; //Fyll i rutorna som upptagna
MLX(nr+1); //Rekursera
for(ii=0;ii<s[nr];ii++) for(jj=0;jj<s[nr];jj++) map[i+ii][j+jj]=0; //Gör rutorna lediga igen
}
}
int main(){
int i,j;
scanf("%d", &N);
for(i=0;i<N;i++) for(j=0;j<N;j++) map[i][j]=0;
min=2*N+1; //Triviallösningen har 2N
MLX(0);
printf("Det behövs minst %d kvadrater.\n", min);
return 0;
}
Här är ett lösningsexempel i Java som testar att lägga ut kvadrater tills stora kvadraten är full. Det är ganska viktigt att vi börjar med att lägga ut stora kvadrater först (i alla fall om man inte sätter min tillräckligt lågt från början), annars kommer vi inte att klara tidsgränsen för storlek 17.
Sedan har vi i exemplet också importerat awt-biblioteket för att få tillgång till klassen Point, så att vi kan "packa in" och "skicka" x- och y-koordinater tillsammans. Värt att nämna är också att matriser i Java fungerar lite annorlunda (och anti-intuitivt) av den anledningen att de i själva verket inte är matriser utan arrayer av arrayer. Vad betyder då det? Jo det betyder att om man vill att "matrisen" ska stämma överens med bilden i ens huvud, så ska man ange y-koordinaten först och x-koordinaten sen. Nu spelar det inte så stor roll, eftersom man alltid kan låtsas att det är tvärtom; och det spelar särskilt ingen roll när det är en kvadrat vi har att göra med. Dock kan det vara en intressant parentes (som får till följd att om man försöker kopiera en "matris" med standardmetoder, så får man inte en kopia, utan en kopia av en array med referenser till arrayer som inte är kopior).
import java.util.*;
import java.awt.*;
public class KvadratPussel
{
//Vår kvadrat som vi ska fylla.
static boolean [][] kvadrat;
//Kvadratens bredd och höjd.
static int N;
//Minsta antalet drag som krävs.
static int min;
//Vår rekursiva metod som testar att lägga ut kvadrater.
//used: Hur många kvadrater vi använt.
public static void rek(int used)
{
//Dumt att fortsätta.
if(used>=min) return;
//Hittar första tomma rutan.
Point p = findFirstEmpty();
//Om svaret var null så betyder det att kvadraten är full
// och vi har funnit den hittills bästa lösningen.
if(p==null)
{
min = used;
}
else //Annars så fortsätter vi att testa lägga ut kvadrater på punkten p.
{
//Vi börjar att testa med större kvadrater. (Det är smartare.)
for(int size = N-1; size>0; size--)
{
//Om det är tillåtet att lägga kvadraten så gör vi det.
if(isValid(p, size))
{
//Lägger kvadraten med storleken size på punkten p.
putQuad(p, size);
//Nu har vi använt en kvadrat och testar att lägga
// på en annan punkt.
rek(used+1);
//Tar bort kvadraten, är ju inte säkert att den är optimal.
removeQuad(p, size);
}
}
}
}
//Metod som letar rätt på en ledig ruta och retunerar dess koordinat i form av en punkt.
public static Point findFirstEmpty()
{
for(int i = 0; i<N; i++) //y-koordinat.
{
for(int j = 0; j<N; j++) //x-koordinat.
{
//Om rutan är ledig så retunerar vi den.
if(!kvadrat[i][j]) return new Point(j,i);
}
}
//Kvadraten är full.
return null;
}
//Retunerar huruvida det är tillåtet att lägga en kvadrat av storlek size
// med sitt övre vänstra hörn i punkten/rutan p. Dvs metoden kollar att
// kvadraten man tänker lägga inte överlappar andra eller går utanför.
public static boolean isValid(Point p, int size)
{
//För stora kvadrater tycker ingen om.
if(p.x + size > N || p.y + size > N) return false;
//Går igenom det område som kvadraten kommer att täcka.
for(int i = p.y; i<p.y+size; i++) //y-koordinat.
{
for(int j = p.x; j<p.x+size; j++) //x-koordinat.
{
//Om rutan redan var upptagen så är draget otillåtet.
if(kvadrat[i][j]) return false;
}
}
//Kvadraten har klarat testerna.
return true;
}
//Lägger en kvadrat av storlek size på punkten/rutan p.
public static void putQuad(Point p, int size)
{
//Markerar de rutor som kvadraten ska täcka som upptagna.
for(int i = p.y; i<p.y+size; i++)
{
for(int j = p.x; j<p.x+size; j++)
{
kvadrat[i][j] = true;
}
}
}
//Tar bort en kvadrat av storlek size som börjar i punkten p.
public static void removeQuad(Point p, int size)
{
for(int i = p.y; i<p.y+size; i++)
{
for(int j = p.x; j<p.x+size; j++)
{
kvadrat[i][j] = false;
}
}
}
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Kvadratens sida: ");
N = scan.nextInt();
//Skapar kvadraten vi ska fylla.
kvadrat = new boolean [N][N];
//Minsta antalet drag som krävs är åtminstone inte
//fler än 2N, vilket är en enkel lösning där man
//bara placerat ut en stor fet kvadrat och övriga
//mindre kvadrater av storlek 1.
min = 2*N;
//Om sidan är jämn så är lösningen trivial.
if(N%2==0)
{
min = 4;
}
else //Annars får vi testa oss fram.
{
//Från början har vi lagt ut noll mindre kvadrater.
rek(0);
}
//Skriver ut svaret.
System.out.println("Det behövs minst " + min + " kvadrater");
}
}