UNDERGROUND CITY

PROBLEM

You are imnprisoned in one of the underground cities in of Cappadocia. Wandering around in the dark to find a way out you find by chance the map of the city. Unfortunately, there is no mark on the map pointing where you are. It is your task to find that out by exploring the city.

The map of the city is a rectangular grid of unit squares. Each square is either an open square, marked with the letter ‘O’, or a part of a wall, marked with the letter ‘W’. The north direction is also shown on the map. Luckily, you have a compass at hand so you can orient the map correctly. Initially, you are on an open square.

Everything starts by calling the procedure (or function) start with no arguments. You can explore the city by using the procedures (or functions) look and move.

You can posinge questions in the form of a procedure (or function) call look(dir) where dir denotes the direction you are looking inat, which can be one of the characters ‘N’, ‘S’, ‘E’ and ‘W’ denoting north, south, east and west, respectively. Now assume the argument dir is ‘N’. The reply will be the character letter ‘O if the square to your north is an open square, and ‘W’ if it is a wall. Similarly, it is possible to look at and get information in about the other directions.neighboring squares.

You can step into one of the four neighboring squares by calling move(dir) where dir denotes the direction of your step as described above. You can only move to an open square. Attempting to move into a wall would be a grave mistake. It is possible to reach any open square of the city starting from any open square.

You are required to find the position of the open square where you found the map by looking (calling look(dir)) minimum number of times. Once you found the position you must report it by calling finish(x,y) where x is the horizontal (west-east) coordinate and y is the vertical (south-north) coordinate of the position.

 

ASSUMPTIONS

  • 31 <= U <=100 where U is the width of the map, i.e. length, in number of squares, of the map in the horizontal (west-east) direction.
  • 31 <=NV <=100 where NV is the height of the map, (i.e. length, in number of squares, of the map in the vertical (south-north) direction.
  • 1 <= M <=100 where M is the width of the map (i.e. length, in number of squares, of the map in the the horizontal (west-east) direction.
  • The city is surrounded with walls, which are included on the map.
  • The south-west corner of the city has the coordinate (1,1) and the north-east corner has the coordinate (U,V)..

 

INPUT

The input is a text file named under.inp.

  • The first line contains two numbers: N, MU, V.
  • Each of the following NV lines: contains a row of the map in the horizontal direction. Each line consists of MU characters, so that the x’th character on the
    (V-y+2)’th line of the input file has information about the position (x,y) of the map: It each of which is either a letter ‘W’ denoting a wall at that position, or a lettern ‘O denoting an open square. [In contrary to integer data, this data has no blanks in between]The data on these lines do not have any blanks in between.

 

OUTPUT

No output file will be generated. The result found by your program must be reported by calling finish(x,y).

 

EXAMPLE

under.jpg (32182 bytes)

INSTRUCTIONS FOR PASCAL PROGRAMMERS

Have the following in your source file:

uses undertpu.tpu;

This tpu will provide the following:

procedure start; { must be called first }

function look (dir:char):char;

procedure move (dir:char);

procedure finish (x,y:integer); { must be called last }

 

INSTRUCTIONS FOR C/C++ PROGRAMMERS

Have the following in your source file:

#include "under.h"

Include under.obj in project. Have the following in your source file:This will provide the following declarations:

void start (void); /* must be called first */

char look (char);

void move (char);

void finish (int,int); /* must be called last */

 

Also o create a project called under which should include your program (under.c or under.cpp) and the library for interaction named underobj.obj. To do this you need to use the project menu of IDE and choose the open option to create a project, and then use add item to include your source file (under.c or under.cpp) and the file underobj.obj.

Use the LARGE memory model compiler option. (Careful: This overrides the memory model mentioned in the Rules of Contest.)

 

EVALUATION

Your program will be allowed to run 5 seconds.

To get full credit the number of calls to look must be the same or less than the number determined by the evaluation program. You can obtain partial credit according to the following formula:

To get full credit, A, for a test case the number of calls to look, x, must be the same or less than or equal to the number, M, set by the evaluation program. Note that M is chosen as larger than (>) the minimum. In particular, M is independent of the clockwise or counter-clockwise ordering of the directions for looking. You can obtain partial credit if the number of calls to look is greater than (>) M but less than (<) twice M. The points you get for a test case is given calculated by rounding to the nearest integer the value obtained by the following formula:

A if x <= M

A/M (2Mx) /M if M < x < 2M

0 if x ³ 2M

Illegal behavior by your program will result in zero points. Illegal behaviors specific to this task are are the following:

  • Calling a a library procedure (or function) with an unacceptable argument, for example a character which does not designate a direction.
  • Attempting to move into a wall.
  • Failing to follow the instructions.

 

HOW TO TRY OUT YOUR PROGRAM

Create a text file called place.txt including the position of the map. Run your program. See the result in the file result.txt.

The file place.txt should have one line having the horizontal and vertical coordinates of the position of the map. You need to create your own input data file under.inp. The result.txt file will contain two lines. The first line will have the arguments x and y for your call to finish (x,y). The second line will have a message of the form "You used look nnn times". Note that this trial is for checking the compatibility of your program with the library. It has nothing to do with the correctness of your solution.

 

GRADING

Your program will be allowed to run 5 seconds.