This week's algorithm from TopCoder Level 550(medium)

[Seabook]

Problem Statement
   
You will be given a list of line segments in an infinite x-y plane. Your method should return how many separate regions there are in the plane once the segments are added. Two points are in the same region if there exists a path from one point to the other that doesn't cross a line segment. The line segments will be given in a String[] lines. Each element of lines will be a single space delimited list of 4 integers. The elements will be formatted as (quotes for clarity) "x0 y0 x1 y1" denoting a line segment from (x0,y0) to (x1,y1). Note that there will always be exactly 1 infinite region that is not completely enclosed by the given line segments. In addition, to make things easier, the line segments will only be horizontal, vertical or diagonal (a diagonal line segment is one whose slope is 1 or -1).
Definition
   
Class:
FaceFinder
Method:
howMany
Parameters:
String[]
Returns:
int
Method signature:
int howMany(String[] lines)
(be sure your method is public)
   

Notes
-
Although the line segment endpoints are bounded by input constraints, when calculating regions, consider the plane to be infinite.
Constraints
-
lines will contain between 1 and 50 elements, inclusive.
-
Each element of lines will contain between 7 and 15 characters, inclusive.
-
Each element of lines will be formatted as "N N N N" where each N represents an integer between 0 and 100 inclusive with no extra leading zeros, and each N is separated by a single space.
-
No line segment will have 0 length.
-
Each line segment will be horizontal, vertical, or diagonal.
-
No two elements of lines will represent the same line segment. This includes cases where one segment goes from point A to point B, and another goes from B to A.
Examples
0)

   
{"0 0 100 100","0 100 100 0"}
Returns: 1
A large X.
1)

   
{"10 10 20 10","10 10 10 20","20 20 10 20","20 20 20 10"}
Returns: 2
A single box.
2)

   
{"0 0 0 10","1 0 1 10","2 0 2 10","3 0 3 10","4 0 4 10",
 "5 0 5 10","6 0 6 10","7 0 7 10","8 0 8 10","9 0 9 10",
 "10 0 10 10","0 0 10 0","0 1 10 1","0 2 10 2","0 3 10 3",
 "0 4 10 4","0 5 10 5","0 6 10 6","0 7 10 7","0 8 10 8",
 "0 9 10 9","0 10 10 10"}
Returns: 101
A 10x10 checkerboard.
3)

   
{"0 0 0 1","0 0 0 2","0 0 0 3","0 0 0 4","0 0 0 5",
 "0 0 1 0","0 0 2 0","0 0 3 0","0 0 4 0","0 0 5 0",
 "5 0 0 5","4 0 0 4","3 0 0 3","2 0 0 2","1 0 0 1"}
Returns: 6
A weird drawing.
4)

   
{"0 0 0 1", "0 0 1 0", "0 0 1 1", "1 0 1 1", "0 1 1 1", "1 0 0 1"}
Returns: 5
This is a 1x1 box with both diagonals filled in.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

[Seabook]

No volunteer to do this week's algorithm? Hopefully some new faces could have a try on this.

Thanks,
Seabook

[Seabook]

Interesting problem. I quickly write a Swing program to represent those dots and lines.
And you can count your self pretty happy then. Haha.

package com.seabook.google.algorithm;

import java.awt.Dimension;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;

public class FaceFinder extends JPanel {
    private static List<Line> lines = new ArrayList<Line>();

    private static String[] lines1 = new String[] { "0 0 100 100",
            "0 100 100 0" };
    private static String[] lines2 = new String[] { "10 10 20 10",
            "10 10 10 20", "20 20 10 20", "20 20 20 10" };
    private static String[] lines3 = new String[] { "0 0 0 10", "1 0 1 10",

            "2 0 2 10", "3 0 3 10", "4 0 4 10", "5 0 5 10", "6 0 6 10",
            "7 0 7 10", "8 0 8 10", "9 0 9 10", "10 0 10 10", "0 0 10 0",
            "0 1 10 1", "0 2 10 2", "0 3 10 3", "0 4 10 4", "0 5 10 5",

            "0 6 10 6", "0 7 10 7", "0 8 10 8", "0 9 10 9", "0 10 10 10" };
    private static String[] line4 = new String[] { "0 0 0 1", "0 0 0 2",

            "0 0 0 3", "0 0 0 4", "0 0 0 5", "0 0 1 0", "0 0 2 0", "0 0 3 0",
            "0 0 4 0", "0 0 5 0", "5 0 0 5", "4 0 0 4", "3 0 0 3", "2 0 0 2",

            "1 0 0 1" };
    private static String[] line5 = new String[] { "0 0 0 1", "0 0 1 0",
            "0 0 1 1", "1 0 1 1", "0 1 1 1", "1 0 0 1" };

    public static void main(String[] args) {
        parseLines(line5);

        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                createAndShowGUI();
            }
        });
    }

    private static void parseLines(String[] pLines) {
        for (String line : pLines) {
            List<Integer> linePoints = new ArrayList<Integer>();
            String[] point = line.split(" ");
            for (String p : point) {
                linePoints.add(Integer.valueOf(p) * 10);
            }
            Line tmpLine = new Line(linePoints.toArray(new Integer[4]));
            lines.add(tmpLine);
        }

    }

    private static void createAndShowGUI() {
        JFrame frame = new JFrame("FaceFinder");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        // Create and set up the content pane.
        FaceFinder newContentPane = new FaceFinder();
        newContentPane.setOpaque(true); // content panes must be opaque
        frame.setContentPane(newContentPane);

        // Display the window.
        frame.pack();
        frame.setVisible(true);
    }

    public FaceFinder() {

    }

    public void paintComponent(Graphics g) {
        super.paintComponent(g);

        for (Line line : lines) {
            int x1 = line.linePoints[0];
            int y1 = line.linePoints[1];
            int x2 = line.linePoints[2];
            int y2 = line.linePoints[3];

            g.drawLine(x1, y1, x2, y2);
        }
    }

    @Override
    public Dimension getPreferredSize() {
        return new Dimension(1000, 1000);
    }
}

class Line {
    Integer[] linePoints = new Integer[4];

    public Line(Integer[] linePoints) {
        this.linePoints = linePoints;
    }

}

[Qu Huanwen]

A stupid solution!


import java.awt.Point;
import java.util.LinkedList;

public class FaceFinder {

    public static void main(String[] args) {

        String[] lines0 = { "0 0 100 100", "0 100 100 0" };
        String[] lines1 = { "10 10 20 10", "10 10 10 20", "20 20 10 20",
                "20 20 20 10" };
        String[] lines2 = { "0 0 0 10", "1 0 1 10", "2 0 2 10", "3 0 3 10",

                "4 0 4 10", "5 0 5 10", "6 0 6 10", "7 0 7 10", "8 0 8 10",
                "9 0 9 10", "10 0 10 10", "0 0 10 0", "0 1 10 1", "0 2 10 2",
                "0 3 10 3", "0 4 10 4", "0 5 10 5", "0 6 10 6", "0 7 10 7",
                "0 8 10 8", "0 9 10 9", "0 10 10 10" };

        String[] lines3 = {"0 0 0 1","0 0 0 2","0 0 0 3","0 0 0 4","0 0 0 5",

                 "0 0 1 0","0 0 2 0","0 0 3 0","0 0 4 0","0 0 5 0",
                 "5 0 0 5","4 0 0 4","3 0 0 3","2 0 0 2","1 0 0 1"};

        String[] lines4 = {"0 0 0 1", "0 0 1 0", "0 0 1 1", "1 0 1 1", "0 1 1 1", "1 0 0 1"};
       
        FaceFinder finder = new FaceFinder();

        System.out.println(finder.howMany(lines0));
        System.out.println(finder.howMany(lines1));
        System.out.println(finder.howMany(lines2));
        System.out.println(finder.howMany(lines3));
        System.out.println(finder.howMany(lines4));
    }

    static final private int M = 4;
    static final private int N = 101*M + 2;
    private int[][] board;

    public int howMany(String[] lines) {
        board = new int[N][N];
        for (String line : lines)
            drawLine(line);

        int color = 1;
        while (fillColor(color))
            color++;

        return color - 1;
    }

    private boolean fillColor(int color) {
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                if (board[y][x] == 0) {
                    fillColorAt(x, y, color);
                    return true;
                }
            }
        }
        return false;
    }

    private void fillColorAt(int x, int y, int color) {
        LinkedList<Point> queue = new LinkedList<Point>();
        queue.addLast(new Point(x, y));

        while (!queue.isEmpty()) {
            Point p = queue.poll();
            x = p.x;
            y = p.y;
            if (x >= 0 && x < N && y >= 0 && y < N && board[y][x] == 0) {
                board[y][x] = color;
                queue.addLast(new Point(x - 1, y));
                queue.addLast(new Point(x + 1, y));
                queue.addLast(new Point(x, y - 1));
                queue.addLast(new Point(x, y + 1));
            }
        }
    }

    private void drawLine(String line) {
        String[] points = line.split(" ");
        int x1 = Integer.parseInt(points[0])*M + 1;
        int y1 = Integer.parseInt(points[1])*M + 1;
        int x2 = Integer.parseInt(points[2])*M + 1;
        int y2 = Integer.parseInt(points[3])*M + 1;
        int dx = x1 == x2 ? 0 : (x1 < x2 ? 1 : -1);
        int dy = y1 == y2 ? 0 : (y1 < y2 ? 1 : -1);
        for (int x = x1, y = y1; x != x2 || y != y2; x += dx, y += dy) {
            board[y][x] = -1;
        }
    }

}

[Seabook]

Beg for the algorithm. Don't quite understand.
If you can provide some comments, that would be awesome.

Thanks,
Seabook

[Huanwen Qu]

It's just a seed fill.

1. Draw the lines in a picture with a certain color.
2. Choose a new color and find a point with no color.
3. Fill color at this point and its adjacent empty points recursively.
4. Repeat step 2 until every point have been filled by some color.
5. Return how many colors is used.

[Seabook]

a seed fill ?

I am curious why you always could pick up a name for the algorithm.
You learn this from school or learn this by yourself from some books?
Or you invented name by yourself?

Thanks,
Seabook