KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

Problem I. 235. (March 2010)

I. 235. Your task is to perform some measurements in a complicated, rectangular-shaped maze. The rectangle is divided into a grid of squares. (Two squares are adjacent only if they have a common edge.) There are two types of squares: solid walls and unit squares that are part of a pathway.

The maze has several entrances and some parts of it may be completely inaccessible from outside. Some parts may be accessed by using a particular entrance but not the other. Each side of the rectangle contains at least one unit of wall.

Your program should determine the area of those parts of the maze that can be accessed from outside. You should also give the total wall length and number of entrances of these parts.

The command line argument to your program is the name of the data file describing the maze. The first line of this file contains the number of rows N (3\leN\le1000) and columns M (3\leM\le1000). The following N lines then contain the actual map. Walls are denoted by F, while squares of a pathway are denoted by a space character.

Your program should use the standard output to display the area of the accessible parts of the maze, the length of walls and number of entrances.

In the example, ``Példa bemenet'' is the sample input, ``Kimenet'' is your output, ``a szürke hátterű mezők a bejárható területet mutatják'' is ``grey squares are parts of the pathways'', ``az útvesztő területe 4 egység'' is ``the area of the maze is 4 units'', ``a falak hossza 10 egység'' is ``the length of walls is 10 units'', while ``az ajtók száma 2 darab'' is ``the number of entrances is 2''.

The source code (i235.pas, i235.cpp, ...) together with a documentation (i235.txt, i235.pdf, ...) -- also describing which developer environment to use for compiling, further a brief description of your solution -- should be submitted in a compressed file (i235.zip).

(10 pont)

Deadline expired on 12 April 2010.


Sorry, the solution is available only in Hungarian. Google translation

Megoldásokról

A feladatra tíz megoldás érkezett. Ezek közül öt teljesen jó, vagy pici pontatlanságot tartalmazott.

A többi program sajnos alapvető hiányosságokat tartalmaz, még a közölt mintabemenetekre is téves megoldást ad. Az útvesztő bejárhatóságának vizsgálatakor fontos volt észrevenni, hogy az nem feltétlenül összefüggő és lehetnek zárt területek. A bejárható pincerendszernek a fal hossza ettől függ. Az ajtók számának meghatározása egyetlen buktatót tartalmazott. Azt, hogy az ajtók a pince sarkában is lehetnek.

A feladat, szokásos módon azt kérte, hogy a program parancssori argumentuma legyen a pincerendszert leíró adatállomány neve. Ezt, az egy utasítással megoldható beállítást, többen végezték el.

Teszt állományok: utveszto1.txt utveszto2.txt utveszto3.txt utveszto4.txt

Mintamegoldás Nagy Miklós (Győr, Révai Miklós Gimnázium) 11. osztályos tanuló megoldását közöljük: i235.pas


Statistics:

10 students sent a solution.
10 points:Balla Attila, Horváth 135 Loránd, Nagy 111 Miklós.
9 points:Barta 111 János, Janosov Milán.
8 points:2 students.
4 points:1 student.
3 points:1 student.
2 points:1 student.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley