[URI ONLINE JUDGE] – 1121 – Sticker Collector Robot

One of the favorite sports in RoboLand is the Robots Rally. This rally is practiced in a giant rectangular arena of square cells with dimensions N rows by M columns. Some cells are empty, some contain a sticker for the World Footbal Cup Album (much appreciated by artificial intelligences in RoboLand) and some are occupied by pillars which support the roof of the arena. During the rally the robots can occupy any cell in the arena, except those containing pillars, since they block the robot movement. The path of the robot in the arena during the rally is determined by a sequence of instructions. Each instruction is represented by one of the following characters: ‘D’, ‘E’ and ‘F’, meaning, respectively, “turn 90 degrees to the right”, “turn 90 degrees to the left” and “move forward one cell”. Robots start the rally in some initial position in the arena and follow closely the sequence of instructions given (after all, they are robots!). Whenever a robot occupies a cell that contains a Cup sticker he collects it. Stickers are not replaced, that is, each scticker can be collected only once. When a robot tries to move into a cell which contains a pillar he stalls, remaining in the cell where he was, with the same orientation. The same happens when a robot tries to leave the arena.

Given the map of the arena, describing the position of pillars and sctickers, and the sequence of instructions of a robot, you must write a program to determine the number of stickers collected by the robot.


The input contains several test cases. The first line of a test case contains three integers N, M and S (1 ≤N, M ≤ 100, 1 ≤ S ≤ 5 × 104 ), separated by white spaces, indicating respectively the number of rows, the number of columns of the arena and the number of instructions to the robot. Each of the following N lines describes a cell line of the arena and contains a string with M characters. The first line to appear in the description of the arena is the one more to the North, the first column to appear in description of a cell line of the arena is the one more to the West.

Each cell in the arena is described by one of the following characters:

  •     `.’ — normal cell;
  •     `*’ — cell which contains a sticker;
  •     `#’ — cell which contains a pillar;
  •     `N’, `S’, `L’, `O’ — cell where the robot starts the rally (only one in the arena). The letter represents the initial robot orientation (North, South, East and West, respectively).

The last line in the input contains a sequence of S characters among `D’, `E’ and `F’, representing the instructions to the robot.

The last test case is followed by a line which contains only three numbers zero separated by a blank space.


For each rally described in the input your program must print a single line containing a single integer indicating the number of stickers that the robot collected during the rally.

Sample Input Sample Output
3 3 2
4 4 5
10 10 20
0 0 0



my solution:


#include <cstdio>
#include <cstring>

using namespace std;

int Dx[] = {-1, 0, 1, 0};
int Dy[] = {0, 1, 0, -1};

int main () {
int N, M, S, posi, posj, i, j, dir, figs;
char grid[102][103], temp, comm[50004];
char ref[4] = {'N', 'L', 'S', 'O'};

while (scanf("%d %d %d", &N, &M, &S) != EOF && N!=0 && M!=0 && S!=0) {
figs = 0;
for (i=0; i < N; i++) {
scanf("%s ", grid[i]);
for (j=0; j < M; j++) {
temp = grid[i][j];
if ( temp == 'N' || temp == 'O' || temp == 'L' || temp == 'S' ) {
posi = i;
posj = j;

for (i = 0; i < 4; i++) {
if (grid[posi][posj] == ref[i]) {
dir = i;
i = 4;

scanf("%s ", comm);

for (i=0; i < S; i++) {
if ( comm[i] == 'E' ) dir = (dir+3)%4;
else if ( comm[i] == 'D' ) dir = (dir+1)%4;
else if (posi + Dx[dir] != N && posj + Dy[dir] != M && posi + Dx[dir] >= 0 && posj + Dy[dir] >= 0) {
temp = grid[posi + Dx[dir]][posj + Dy[dir]];

if ( temp != '#' ) {
grid[posi][posj] = '.';
if( temp == '*' ) figs++;
posi += Dx[dir];
posj += Dy[dir];

printf("%d\n", figs);

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s