Pages

▼

Thursday, September 17, 2015

BitMap (KICTM UiTM Jasin 2015)

This problem requires you to search a black and white satellite image of a desert for a secret building complex with a given shape.  A complex of this given shape may host an installation for producing the strategic xeenium macgillicudamate ingredient, and must keep its orientation with regard to cardinal axes (North-East-South-West).  Rotations and mirror images are not allowed because they would interfere with the delicate alchemy required for the production process.  You must determine how many times the given complex may possibly occur in the image.

Consider the following images, both on the same scale, where a # (sharp) is a “black” pixel representing a part of a building, and a . (dot) is a “white” pixel, representing sand.  On the left is an image of the complex you are trying to locate, on the right is an image of the desert with some buildings on it.



  • How many possible locations for the given secret buildings do we count?.
  • The answer is four: one at the top-left corner, two overlapped possibilities to its right, and one in the bottom right.  The shapes near the top-right corner, and in the centre bottom don’t count because they are rotated (remember that rotated and/or mirrored images do not count).
  • Note that, as this answer implies, the sand pixels in the image of the building complex simply establish the necessary relationships between the building parts.  In the actual image they may contain either sand or other building parts (possibly for disguising the true nature of the complex).
  • Assume that images representing strategic complexes are already trimmed of any unneeded dot “white” pixels on the edges, ie, these images will always contain at least one # character on each edge (as our example shows).  An edge here is the first or last row or column. 


INPUT 
Each problem will give you the specification for the building complex image followed by the specification for the desert image.  There may be several problems in the input data, which will be terminated by a line containing just 0 0.  In each problem the input is: 
  • Line 1:  2 positive integers, B1, B2, respectively representing the number of lines and the numbers of columns in the following Buildings image.  Both numbers will be in the range 1 to16 inclusive. 
  • Next B1 lines:  B2 characters (# or .) on each line to represent part of the image of the building complex.
  • Next Line:  2 positive integers, D1, D2, respectively representing the number of lines and the numbers of columns in the following Desert image.  Both numbers will be in the range 1 to 64 inclusive.
  • Next D1 lines:  D2 characters (# or .) on each line to represent the desert image.

Output
The output will consist of one integer for each problem given, on a line by itself, with no spaces, giving the number of possible occurrences of the given building complex.

Sample Input

 Sample Output

4
3
4

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.*;
import java.lang.*;

public class Q1 {

    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        String line = System.getProperty("line.separator");
        scan.useDelimiter(line);
        char[][] map, pattern;

        pattern = readMap(scan);
        while (pattern.length != 0) {
            map = readMap(scan);
            System.out.println(countPattern(map, pattern));
            pattern = readMap(scan);
        }
    }

    public static boolean findPattern(char[][] map, char[][] pattern, int[] offset) {
        for (int y = 0; y < pattern.length; y++) {
            for (int x = 0; x < pattern[y].length; x++) {
                if ((y + offset[0] >= map.length) || (x + offset[1] >= map[y].length)) {
                    return false;
                }

                if ((pattern[y][x] == '#') && (map[y + offset[0]][x + offset[1]] != '#')) {
                    return false;
                }
            }
        }

        return true;
    }

    public static int countPattern(char[][] map, char[][] pattern) {
        int count = 0;
        for (int y = 0; y < map.length - pattern.length + 1; y++) {
            for (int x = 0; x < map[0].length - pattern[0].length + 1; x++) {
                int[] offset = new int[] {
                    y, x
                };
                if (findPattern(map, pattern, offset)) {
                    count++;
                }
            }
        }
        return count;
    }

    public static char[][] readMap(Scanner scan) {
        int rows, columns;
        char[][] map;

        String[] line = scan.next().split(" ");
        rows = Integer.parseInt(line[0]);
        columns = Integer.parseInt(line[1]);

        map = new char[rows][columns];

        for (int x = 0; x < map.length; x++) {
            String str = scan.next();
            for (int y = 0; y < map[x].length; y++) {
                map[x][y] = str.charAt(y);
            }
        }
        return map;
    }
}
at

No comments:

Post a Comment