Tävlingsprogrammering/Uppgifter/Väggreparation

Väggreparation (PO-onlinekvalet 2008)

Framsidan av mitt hus är täckt med dekorativa kvadratiska brickor. Jag är dock orolig att några av brickorna inte sitter fast ordentligt och riskerar att ramla ner. Jag vill stadga upp de nuvarande brickorna så att väggen blir stabil. I figuren nedan är de ursprungliga brickorna svarta och de lediga utrymmena på väggen vita.

Väggen blir stabil om varje bricka är uppstadgad hela vägen från marken. För att fixa väggen ovan skulle jag behöva åtta brickor i de streckade positionerna nedan.

Givet en vägg, beräkna det minsta antalet brickor som krävs för att stadga upp de ursprungliga brickorna.

Indata

På första raden står två heltal: höjden (1 ≤ h ≤ 20) och bredden (1 ≤ w ≤ 40) på väggen. Därefter följer h rader, var och en innhållande en sträng bestående av exakt w tecken. Varje tecken i strängen är antingen ett 'X' (en bricka) eller ett '.' (ett ledigt utrymme). Den sista raden motsvarar den del av väggen som är närmast marken.

Utdata

Programmet ska skriva ut en rad med ett heltal: det minsta antal brickor jag behöver inhandla för att stadga upp de redan existerande brickorna.

Exempel: Indata

4 12
..X...X.....
....X.X...XX
...........X
..X.......X.

Exempel: Utdata

8

Lösning

Det här är ett enkelt problem som inte kräver någon avancerad algoritm. Det gäller att inse att alla rutor under en bricka måste fyllas ut (om där inte redan finns en bricka).

Så för varje kolumn gäller det att hitta den översta brickan, och sedan räkna hur många rutor under denna bricka i samma kolumn som är tomma (dessa måste fyllas ut). Allt detta kan göras med två for-loopar.

Lösningsexempel i C#:

using System.IO;

public class Uppgift1
{
    public static void Main(string[] args)
    {
        Solve(new StreamReader("vaggreparering1.in"), Console.Out);
    }
    
    public static void Solve(TextReader tr, TextWriter tw)
    {
        string[] size = tr.ReadLine().Split(' ');
        int ysize = int.Parse(size[0]);
        int xsize = int.Parse(size[1]);
        int required = 0;
        bool[] fill = new bool[xsize];
        for (int y = 0; y < ysize; y++)
        {
            string s = tr.ReadLine();
            for (int x = 0; x < xsize; x++)
            {
                if (s[x] == 'X')
                    fill[x] = true;
                else if (fill[x])
                    required++;
            }
        }
        tw.WriteLine(required);
    }
}

Exempellösning i Java:

import java.io.*;
public class main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		int a = Integer.parseInt(s.split(" ")[0]);
		int b = Integer.parseInt(s.split(" ")[1]);
		String[] f = new String[20];
		for(int i = 0;i<a;i++){
			f[i] = br.readLine();
		}
		int antal = 0;
		boolean x = false;
		for(int i = 0;i<b;i++){
		for(int j = 0;j<a;j++){
			if(f[j].charAt(i) == 'X' && !x){
				x = true;
				antal += a-j-1;
			}
			else if(f[j].charAt(i) == 'X'){
				antal--;
			}
		}
		x = false;
		}
		System.out.print(antal);
	}
}