Tävlingsprogrammering/Uppgifter/Kvadrater
Kvadrater
Pelle ritar ett antal fyllda kvadrater i olika färger i sitt favoritritprogram Paint. Varje ny kvadrat han ritar kan helt eller delvis täcka en tidigare ritad kvadrat. Den nya kvadraten täcker då givetvis helt över de delar av den undre som den överlappar. Det är därför inte säkert att man i efterhand kan veta den exakta storleken på de kvadrater Pelle ritade. Givet hur hans konstverk ser ut efter att alla kvadrater har ritats, bestäm den största storlek som varje kvadrat ursprungligen kan ha haft.
Indata
Första raden i filen kvadrat.dat består av två heltal, N (1 ≤ N ≤ 1, 000), storleken på ritytan (som också är kvadratisk), och M (1 ≤ M ≤ 9), antalet kvadrater Pelle ritade. Därefter följer N rader som beskriver bilden efter att alla kvadrater har ritats. Varje rad innehåller N tecken, där en punkt motsvarar en pixel som inte blivit täckt av någon kvadrat, och där en siffra motsvarar en pixel som täckts av minst en kvadrat (där siffran motsvarar den senast ritade av dessa). Siffran 1 betecknar den första kvadraten som ritades o.s.v., upp till siffran M.
Utdata
För varje kvadrat som ritats, skriv ut den största storleken den kan tänkas ha haft, talen separerade med blanksteg. Du kan utgå ifrån att bilden i indatat går att skapa genom att rita M kvadrater. Tänk också på att en kvadrat kan ha helt täckts av en eller flera andra kvadrater.
Exempel
10 7 .......... .7..1111.. ..224441.. ..224441.. ..224441.. .6666655.. .6666655.. .6666655.. .6666655.. .66666....
Svar
4553451
Förklaring: Kvadrat 3, som inte syns längre, kan helt gömma sig bakom kvadrat 6. Kvadrat 2 måste ha minst längd 3, men kan ha ända upp till längd 5 om den gömmer sig bakom kvadrat 4, 5 och 6. Dock inte längd 6 eftersom den då skulle behöva sudda ut några pixlar från kvadrat 1.
Lösning[redigera]
För att lösa denna uppgift hjälper det att känna till hur man löser följande enklare problem: Givet ett rutnät (NxN stort) där vissa rutor är tomma ('.') och vissa är ifyllda ('#'), hur stor är den största kvadraten med fyllda rutor?
Det problemet kan man lösa med dynamisk programmering, vilket enbart kräver att man loopar över rutorna en gång. Kalla rutnätet för A, där A(x,y) = 1 om rutan är fylld och A(x,y) = 0 om rutan är tom. Låt rutan uppe i det vänstra hörnet ha koordinaterna 1,1. Vi definierar funktionen f(x,y) som den största kvadrat där det nedre högra hörnet ligger i ruta x,y. Dvs, om f(x,y) = 2 så måste A(x-1,y) = A(x-1,y-1) = A(x,y) = A(x,y-1) = 1. Vi vill nu hitta ett snabbt sätt att beräkna f(x,y). Om A(x,y) = 0 så är förstås f(x,y) = 0, så från och med nu antar vi att A(x,y)=1.
Genom att först beräkna f(x-1,y) och f(x,y-1) så får vi en hel del information om vad f(x,y) kan vara. Om f(x-1,y)=3 och f(x,y-1)=5 t ex kan f(x,y) aldrig vara mer än 4, för då skulle f(x-1,y) behöva vara minst 4. Faktum är att vi kan (med hjälp av en figur) lätt inse att om f(x-1,y) != f(x, y-1), så kommer f(x,y) alltid vara min(f(x-1,y), f(x,y-1))+1. Om f(x-1,y) = f(x,y-1) så kan vi inte riktigt dra den slutsatsen, för vi måste också verifiera att rutan x-z+1, y-z+1 är fylld. [TODO: en figur eller två gör detta mycket tydligare] Koden för att beräkna detta blir således:
for(int y=1;y<=N;y++)
for(int x=1;x<=N;x++)
if A(x,y) == 1
if x==1 or y == 1
f(x,y) = 1
else if f(x-1,y) != f(x,y-1)
f(x,y) = min(f(x-1,y), f(x,y-1)) +1
else if A(x-f(x-1,y)+1,y-f(x-1,y)+1) == 1
f(x,y) = f(x-1,y) + 1
else
f(x,y) = f(x-1,y)
Tillbaka till ursprungsproblemet. I princip använder vi algoritmen ovan en gång för varje ritad kvadrat. Antag att det ritats 6 kvadrater och att vi vill beräkna hur stor kvadrat 3 kan ha varit. Delar av kvadrat 3 kan gömma sig bakom rutorna 3, 4, 5 och 6 men inga andra rutor. Vi använder då av algoritmen ovan, där rutorna 3,4,5,6 betraktas som fyllda och de andra som tomma. Vi letar rätt på den största kvadraten som kan finnas i detta rutnät, men ignorerar alla sådana som inte helt innesluter alla 3:or i den ursprungliga matrisen. Detta upprepas för alla siffror i ursprungsmatrisen, så algoritmen ovan kommer att exekveras högst 9 gånger. Den slutliga lösningen kan se ut så här:
#include <iostream>
using namespace std;
const int MAX_SIZE = 1000;
int a[MAX_SIZE+1][MAX_SIZE+1];
char map[MAX_SIZE][MAX_SIZE+1];
int main()
{
int size, n;
cin >> size >> n;
for(int i=0;i<size;i++) cin >> map[i];
for(int q=0;q<n;q++) {
int largest = 0, x1 = size, x2 = 0, y1 = size, y2 = 0;
for(int y=0;y<size;y++)
for(int x=0;x<size;x++)
if (map[y][x] == '1'+q) {
x1 = min(x1, x);
x2 = max(x2, x);
y1 = min(y1, y);
y2 = max(y2, y);
}
for(int y=0;y<size;y++)
for(int x=0;x<size;x++) {
bool ok = map[y][x] != '.' && map[y][x] >= ('1'+q);
if (!ok)
a[y][x] = 0;
else if (x == 0 || y == 0)
a[y][x] = 1;
else {
a[y][x] = min(a[y-1][x], a[y][x-1]) + 1;
if (a[y-1][x] == a[y][x-1] && !a[y-a[y][x]+1][x-a[y][x]+1])
a[y][x]--;
}
if (x1 > x2 || (x1 >= x - a[y][x] + 1 && x2 <= x && y1 >= y - a[y][x] + 1 && y2 <= y))
largest = max(largest, a[y][x]);
}
cout << largest << (q < n-1 ? " " : "\n");
}
return 0;
}
Liknande lösning i Java, fast vi använder oss av det övre vänstra hörnet istället och fyller i punkterna där vi kan dra vår kvadrat allt efter som. Sedan för att kolla om kvadraten är giltig så skapar vi en minsta möjlig rektangel som innehåller alla punkter kvadraten måste innehålla och kollar om kvadraten innehåller den rektangeln.
import java.util.*;
import java.io.*;
import java.awt.*;
public class Kvadrater
{
//Markerar de rutor där man kan dra kvadrater. Dvs OK.
static boolean [][] field;
//Sparar den största kvadrat man kan skapa med övre vänstra
//hörnet i punkt [y][x].
static int [][] square;
//Markerar de rutor/punkter som ska vara OK.
public static void mark(LinkedList <Point> points)
{
for(Point p : points)
{
field[p.y][p.x] = true;
}
}
//Retunerar storleken av den största kvadrat med övre vänstra
//hörn i punkten/rutan [y][x].
public static int big(int x, int y)
{
//Största kvadraten i en otillåten ruta är 0.
if(x>=field.length || y>=field.length || !field[y][x]) return 0;
//Har vi redan räknat ut svaret behöver vi inte göra det igen.
if(square[y][x]!=0) return square[y][x];
//Räknar ut största kvadraten för respektive två punkter.
int s1 = big(x, y+1);
int s2 = big(x+1, y);
//Om rutan i nedre högra hörnet är OK. (Då om s1==s2.)
boolean z = field[y+s1][x+s2];
//Avgör storleken utifrån informationen.
square[y][x] = (s1!=s2) ? Math.min(s1, s2) + 1 : (z) ? s1+1 : s1;
return square[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 kvadrat.dat i mappen/katalogen data.
Scanner scan = new Scanner(new File("data\\kvadrat.dat"));
//Storleken på ritytan.
int N = scan.nextInt();
//Antalet kvadrater.
int M = scan.nextInt();
//Skapar ritytan.
field = new boolean [N][N];
//Sparar de punkter som ingår i en viss kvadrat.
@SuppressWarnings("unchecked")
LinkedList <Point> [] points = new LinkedList [M+1];
//Skapar listor så vi kan lagra punkterna.
for(int i = 1; i<=M; i++) points[i] = new LinkedList <Point> ();
//Sparar de punkter som ligger högst upp, längst till vänster, längst
//ner respektive längst till höger i den synliga delen av kvadraten.
//[0][i] = min(y), [1][i] = min(x), [2][i] = max(y), [3][i] = max(x).
Point [][] minRec = new Point [4][M+1];
//Läser in rutorna/punkterna.
for(int i = 0; i<N; i++)
{
//Läser in raden.
String s = scan.next();
//Går igenom raden.
for(int j = 0; j<N; j++)
{
char c = s.charAt(j);
//Om det är en siffra.
if(c!='.')
{
//Sparar punkten i tillhörande kvadrat.
Point p = new Point(j, i);
//Kan du char-aritmetik så fattar du.
//(Ex: '0'= 48, '4' = 52. '4'-'0' = 52 - 48 = 4.)
points[c-'0'].add(p);
//Kollar om detta är någon sidopunkt.
if(minRec[0][c-'0']!=null)
{
if(i<minRec[0][c-'0'].y) minRec[0][c-'0'] = p;
}
else minRec[0][c-'0'] = p;
if(minRec[1][c-'0']!=null)
{
if(j<minRec[1][c-'0'].x) minRec[1][c-'0'] = p;
}
else minRec[1][c-'0'] = p;
if(minRec[2][c-'0']!=null)
{
if(i>minRec[2][c-'0'].y) minRec[2][c-'0'] = p;
}
else minRec[2][c-'0'] = p;
if(minRec[3][c-'0']!=null)
{
if(j>minRec[3][c-'0'].x) minRec[3][c-'0'] = p;
}
else minRec[3][c-'0'] = p;
}
}
}
//Markerar punkterna i sista kvadraten i ritytan.
mark(points[M]);
Point p1 = points[M].getLast(), p2 = points[M].getFirst();
//Storleken för den är trivial, då den är helt synlig.
int big = p1.x - p2.x + 1;
//Lagrar svaret.
String svar = ""+big;
//Beräknar största kvadrat för respektive kvadrat.
for(int i = M-1; i>0; i--)
{
//Markerar de synliga punkterna av kvadraten.
mark(points[i]);
//En rektangel av minimal storlek som innehåller
//alla de punkter som kvadraten måste innehålla.
Rectangle rec = null;
//Skapar denna minimala rektangel.
if(minRec[0][i]!=null)
{
int x = minRec[1][i].x;
int y = minRec[0][i].y;
int w = minRec[3][i].x - minRec[1][i].x + 1;
int h = minRec[2][i].y - minRec[0][i].y + 1;
rec = new Rectangle(x, y, w, h);
}
//Om minimala rektangelna är null, så syns inga punkter av
//kvadraten och svaret är den tidigare största kvadraten.
int size = (rec==null) ? big : 0;
//Är size skiljt från 0 har vi redan svaret.
if(size==0)
{
//Nollställer största kvadrater för ritytan.
//För nu med nya rutor till vårt förfogande behöver inte
//de gamla svaren gälla.
square = new int [N][N];
//Kollar den största kvadraten i alla relevanta punkter.
for(int j = i; j<=M; j++)
{
for(Point p : points[j])
{
//Kollar största kvadraten.
int tmp = big(p.x, p.y);
//Skapar en Rectangle-representation av den.
Rectangle quad = new Rectangle(p.x, p.y, tmp, tmp);
//Kolla om detta är den största kvadraten
if(tmp>big) big = tmp;
//Kollar om den är större än tidigare största och
//om den därtill är godkänd. Dvs innehåller alla
//punkter kvadraten måste innehålla.
if(tmp>size && quad.contains(rec)) size = tmp;;
}
}
}
svar = size + " " + svar;
}
//Skriver ut svaret.
System.out.println("Största möjliga kvadrater: " + svar);
}
}