Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1121
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1121
Sticker Collector Robot
Maratona de Programação da SBC 
Brazil
Timelimit: 1
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.
Input
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.
Output
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.
| Input Sample | Output Sample |
|
3 3 2 |
0 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int n, m, s, lin, col, pi, pj, fig, h, vi, vj;
short proc;
char mp[101][101];
char it[50001];
while (scanf("%d %d %d", &n, &m, &s) == 3 && n+m+s) {
while (getchar() != '\n');
proc = 1;
for (lin = 0; lin < n; ++lin) {
for (col = 0; col < m; ++col) {
scanf("%c", &mp[lin][col]);
if (proc && mp[lin][col] == 'N' || mp[lin][col] == 'S' || mp[lin][col] == 'L' || mp[lin][col] == 'O') {
pi = lin; pj = col; proc = 0;
}
}
while (getchar() != '\n');
}
scanf("%s", &it);
fig = 0;
for (h = 0; h < s; ++h) {
if (it[h] == 'D' && mp[pi][pj] == 'N') mp[pi][pj] = 'L';
else if (it[h] == 'D' && mp[pi][pj] == 'L') mp[pi][pj] = 'S';
else if (it[h] == 'D' && mp[pi][pj] == 'S') mp[pi][pj] = 'O';
else if (it[h] == 'D' && mp[pi][pj] == 'O') mp[pi][pj] = 'N';
else if (it[h] == 'E' && mp[pi][pj] == 'N') mp[pi][pj] = 'O';
else if (it[h] == 'E' && mp[pi][pj] == 'O') mp[pi][pj] = 'S';
else if (it[h] == 'E' && mp[pi][pj] == 'S') mp[pi][pj] = 'L';
else if (it[h] == 'E' && mp[pi][pj] == 'L') mp[pi][pj] = 'N';
else {
if (mp[pi][pj] == 'N') { vi = pi-1; vj = pj; }
else if (mp[pi][pj] == 'O') { vi = pi; vj = pj-1; }
else if (mp[pi][pj] == 'S') { vi = pi+1; vj = pj; }
else if (mp[pi][pj] == 'L') { vi = pi; vj = pj+1; }
if (0 < = vi && vi < n && 0 <= vj && vj < m && mp[vi][vj] != '#') {
if (mp[vi][vj] == '*') ++fig;
mp[vi][vj] = mp[pi][pj];
mp[pi][pj] = '.';
pi = vi; pj = vj;
}
}
}
printf("%d\n", fig);
}
return 0;
}
Input
***
*N*
***
DE
4 4 5
...#
*#O.
*.*.
*.#.
FFEFF
10 10 20
....*.....
.......*..
.....*....
..*.#.....
...#N.*..*
...*......
..........
..........
..........
..........
FDFFFFFFEEFFFFFFEFDF
0 0 0
Output
1
3
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,m,s;
while(cin >> n >> m >> s){
if(n == 0 && m == 0 && s == 0)break;
vector < string> str(n);
int I=-1,J=-1;
int position;
for(int i = 0; i < n; i++)
{
cin >> str[i];
for(int j = 0; j < str[i].length(); j++)
{
if(str[i][j] == 'N')
{
I = i;J = j;
position = 1;
// break;
}
if(str[i][j] == 'S')
{
I = i; J = j;
position = 3;
//break;
}
if(str[i][j] == 'L')
{
I = i; J = j;
position = 2;
//break;
}
if(str[i][j] == 'O')
{
I=i;J=j;
position = 4;
//break;
}
}
}
//cout << str[I][J] << " I="<<I << " J=" << J << " Position=" << position << endl;
//cout << "------------------------------------------------\n";
string command;
cin >> command;
int index = 0;
int card = 0;
for(;index < command.length(); index++)
{
if(str[I][J] == '*')
{
card++;
str[I][J]='.';
}
if(command[index] == 'F')
{
if(position == 1>
{
if(I-1 >= 0&&str[I-1][J]!='#')
{
I--;
}
}
else if(position==3)
{
if(I+1 < n && str[I+1][J] != '#')
{
I++;
}
}
else if(position == 2)
{
if(J+1 < m && str[I][J+1] != '#')
{
J++;
}
}
else if(position==4>
{
if(J-1 >= 0 && str[I][J-1] != '#')
{
J--;
}
}
}
else if(command[index]=='D')
{
if(position==1)position=2;
else if(position==2)position=3;
else if(position==3)position=4;
else if(position==4)position=1;
}
else if(command[index]=='E')
{
if(position==1)position=4;
else if(position==4)position=3;
else if(position==3)position=2;
else if(position==2)position=1;
}
//cout << str[I][J] << " I=" << I << " J=" << J << " Position=" << position << endl;
}
if(str[I][J]=='*')
{
card++;
str[I][J]='.';
}
cout << card << endl;
}
return 0;
}
Input
***
*N*
***
DE
4 4 5
...#
*#O.
*.*.
*.#.
FFEFF
10 10 20
....*.....
.......*..
.....*....
..*.#.....
...#N.*..*
...*......
..........
..........
..........
..........
FDFFFFFFEEFFFFFFEFDF
0 0 0
Output
1
3
#3 Code Example with Python Programming
Code -
Python Programming
while True:
n, m, s = [int(x) for x in input().split()]
if n == m == s == 0: break
mp, proc = [], True
for g in range(n):
q = [y for y in input()]
if proc:
for c, s in enumerate(q):
if s in 'NSLO': px, py, proc = g, c, False
mp.append(q)
it = input()
fig = 0
for h in it:
if h == 'D' and mp[px][py] == 'N': mp[px][py] = 'L'
elif h == 'D' and mp[px][py] == 'L': mp[px][py] = 'S'
elif h == 'D' and mp[px][py] == 'S': mp[px][py] = 'O'
elif h == 'D' and mp[px][py] == 'O': mp[px][py] = 'N'
elif h == 'E' and mp[px][py] == 'N': mp[px][py] = 'O'
elif h == 'E' and mp[px][py] == 'O': mp[px][py] = 'S'
elif h == 'E' and mp[px][py] == 'S': mp[px][py] = 'L'
elif h == 'E' and mp[px][py] == 'L': mp[px][py] = 'N'
else:
if mp[px][py] == 'N': ix, iy = px-1, py
elif mp[px][py] == 'O': ix, iy = px, py-1
elif mp[px][py] == 'S': ix, iy = px+1, py
elif mp[px][py] == 'L': ix, iy = px, py+1
if 0 <= ix < n and 0 <= iy < m and mp[ix][iy] != '#':
if mp[ix][iy] == '*': fig += 1
mp[ix][iy] = mp[px][py]
mp[px][py] = '.'
px, py = ix, iy
print(fig)
Input
***
*N*
***
DE
4 4 5
...#
*#O.
*.*.
*.#.
FFEFF
10 10 20
....*.....
.......*..
.....*....
..*.#.....
...#N.*..*
...*......
..........
..........
..........
..........
FDFFFFFFEEFFFFFFEFDF
0 0 0
Output
1
3