UVa 201

From Algorithmist
Jump to navigation Jump to search

201 - Squares[edit]

Summary[edit]

Bruteforce. Since , we can simply iterate all the possible squares.

Explanation[edit]

We can think that vertical or horizontal lines are edges between two adjecent point. After that we can take a three dimensional array (say a [N][N][2]) to store the count of horizontal(a[i][j][0]) edges and vertical(a[i][j][1]) edges. a[i][j][0] contains number of horizontal edges at row i upto coloumn j. and a[i][j][1] contains number of vertical edges at coloumn j upto row i. Next you use a O(n^2) loop to find a square. a square of size 1 is found if there is an edge from (i,j) to (i,j+1) and (i,j+1) to (i+1,j+1) and (i,j) to (i+1,j) and (i+1,j) to (i+1,j+1) we can get this just by subtarcting values calculated above.

Input[edit]

4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1
4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1
4
16
H 1 1
H 1 3
H 2 1
H 2 2
H 2 3
H 3 2
H 4 2
H 4 3
V 1 1
V 2 1
V 2 2
V 2 3
V 3 2
V 4 1
V 4 2
V 4 3
2
3
H 1 1
H 2 1
V 2 1

Output[edit]

Problem #1

2 square (s) of size 1
1 square (s) of size 2

**********************************

Problem #2

No completed squares can be found.

**********************************

Problem #3

2 square (s) of size 1
1 square (s) of size 2

**********************************

Problem #4

No completed squares can be found.

**********************************

Problem #5

2 square (s) of size 1
1 square (s) of size 2

**********************************

Problem #6

No completed squares can be found.