ARCHI - Architecture

Architecture, a tightrope walk between engineering and art! There are probably few invariants shared by the architectural styles around the world and throughout time. Precisely this diversity makes the domain so interesting and challenging.

 

 

Any domains may serve as sources of inspiration, mathematical shapes, nature, organisms and even arched slices of Swiss cheese J. Some of our university friends from architecture plan to participate in the prestigious Erect a Palace From Lines (EPFL) contest. This contest is about designing a huge single-floor palace by building horizontal and vertical walls inside the preset square fundament.

The students just finished their creative prototypes, and you are to revise their projects before they enter the contest. Some were obviously overwhelmed by the cryptographic protocol required for the palace description and do not know how many rooms their palace has. Walls are one unit thick and are described by their horizontal and vertical start and end positions. As the palace is huge, these coordinates are expressed in a base 26 system (the latin alphabet). Having overlapping walls is not a problem. For the encryption, read ‘A’ as zero and ‘Z’ as twenty-five. All other letters cover the remaining range in the conventional lexicographic order.

 

INPUT

The input consists of several test-cases, separated by an empty line. Each test-case starts with the side length of the square palace n (A<=n<=ZZ) and the number of walls w (0<=w<=500) the student placed inside the palace. The palace’s interior spreads thus from 0 to n-1, vertically and horizontally. The following w lines each describe a wall in the form x1 y1 x2 y2, the horizontal and vertical endpoints of the wall such that (0<=x1,y1,x2,y2<=n-1). Input terminates on a test-case with n=A and w=0, which must not be processed. You may safely assume that no student placed walls that transgress the fundaments of the palace and that no palace has more than 10’000 rooms.

 

OUTPUT

For each test-case, output the number of rooms in the palace.

 

SAMPLE INPUT

P 17

G N G F

F G C G

F O F K

G M N M

C F C M

I E K E

O C O E

B L B N

J M J E

M O J O

H O C O

L H L I

N F K F

M E O E

N D O D

E C E L

G O G L

 

ZZZZZZZZZZZZZZZZ 4

A GH ZZZZZZZZZZZZZZZY GH

POLYPROG SELECTION POLYPROG CONTEST

TOBE ORNOT TOBE THATSTHEQUESTION

LEADINGZEROS NO LEADINGAS NO

 

SAMPLE OUTPUT

 

4

2


Added by:Christian Kauth
Date:2010-10-23
Time limit:1.678s-5.232s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2011-05-27 21:04:32 :D
It seems that one test file has n=A and w=0 at the end and another has not. Implement ending on both EOF and the above condition.
2010-11-03 07:11:20 Christian Kauth
The test-data has been slightly relaxed and all submissions so far rejudged.

Last edit: 2010-11-03 07:11:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.