SketchGame

SRM 80 · 2002-04-15 · by lbackstrom

SRM 80 · 2002-04-15 · by lbackstrom · Simulation

Show categories

Class Name: SketchGame

Return Type: String[]

Method Name: draw

Arg Types: (vector<string>, int, int)

Problem Statement

In an old video game, you are presented with a board which is x units wide, and y units high. The board is composed of x*y one by one squares and each of these squares has two possible states, on or off. The player in the game starts in the most northwestern corner at x = 0 and y = 0 and initially all the squares are in the off state. As the player moves around, each time he moves onto a new one by one square, that square's state toggles. So, if it was off it becomes on, and vice versa.

Your task is, given a String[] containing all of the information about how the player moves about on the board, and the dimensions of the board, x and y, return the final state of all the one by one squares.

The input String[], moves, will contain a list of movements in 1 of the four cardinal directions.
'N' is for north and indicates a move in the negative y direction.
'E' is for east and indicates a move in the positive x direction.
'S' is for south and indicates a move in the positive y direction.
'W' is for west and indicates a move in the negative x direction.
Each String in moves will start with one of these 4 characters, followed immediately by the number of tiles to move in that direction. Thus "N4" indicates a move of 4 tiles in the negative y direction.

Your method must execute all of these moves in the order they appear (i.e., element 0 first) and return a String[] with y elements, each of which has x characters where a '1' (the number one, not lowercase 'L') represents an on state, and a '0' (the number zero, not the letter oh) represents the off state.

Notes

states only toggle when stepping onto a new tile. When leaving a tile, or staying on a tile, the state of that tile does not change.
if a move would take the player off the board, instead he bumps into the wall and stops. (see example 2)
x is the number of characters that each String in the return must contain.
y is the number of elements in the return String[].
The initial state of all sqaures is off.

Constraints

x and y are both in the range 1 to 50, inclusive.
moves has between 0 and 50 elements, inclusive.
Each element of moves contains a single letter ('N','E','S', or 'W') followed by an integer between 0 and 100, inclusive (no leading '0's).

Examples

{"E1","S2","N2","S2","N1","E3","W3","E3","S4","N4","S3","N3","S2","N2","S1","N1","E1","W1","E2","W1","E2","W1","E3","W1","E1","S3","E1","S1","E3","N1","E1","N3","S2","N1","W1","N1","W3","E4","W3"}
50
50
Returns: { "00000000000000000000000000000000000000000000000000",  "01111110001111000000000000000000000000000000000000",  "00001000010001100000000000000000000000000000000000",  "00001000010000000000000000000000000000000000000000",  "00001000011001100000000000000000000000000000000000",  "00001000001111000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000",  "00000000000000000000000000000000000000000000000000" }

{"E1","S2","N2","S2","N1","E3","W3","E3","S4","N4","S3","N3","S2","N2","S1","N1","E1","W1","E2","W1","E2","W1","E3","W1","E1","S3","E1","S1","E3","N1","E1","N3","S2","N1","W1","N1","W3","E4","W3"}
16
7
Returns: { "0000000000000000",  "0111111000111100",  "0000100001000110",  "0000100001000000",  "0000100001100110",  "0000100000111100",  "0000000000000000" }

{"E1","S2","N2","S2","N1","E3","W3","E3","S4","N4","S3","N3","S2","N2","S1","N1","E1","W1","E2","W1","E2","W1","E3","W1","E1","S3","E1","S1","E3","N1","E1","N3","S2","N1","W1","N1","W3","E4","W3"}
1
1
Returns: { "0" }

{"E1","S2","N2","S2","N1","E3","W3","E3","S4","N4","S3","N3","S2","N2","S1","N1","E1","W1","E2","W1","E2","W1","E3","W1","E1","S3","E1","S1","E3","N1","E1","N3","S2","N1","W1","N1","W3","E4","W3"}
15
15
Returns: { "000000000000000",  "011111100011110",  "000010000100011",  "000010000100000",  "000010000110011",  "000010000011110",  "000000000000000",  "000000000000000",  "000000000000000",  "000000000000000",  "000000000000000",  "000000000000000",  "000000000000000",  "000000000000000",  "000000000000000" }

{"E1","S2","N2","S2","N1","E3","W3","E3","S4","N4","S3","N3","S2","N2","S1","N1","E1","W1","E2","W1","E2","W1","E3","W1","E1","S3","E1","S1","E3","N1","E1","N3","S2","N1","W1","N1","W3","E4","W3","N0"}
16
7
Returns: { "0000000000000000",  "0111111000111100",  "0000100001000110",  "0000100001000000",  "0000100001100110",  "0000100000111100",  "0000000000000000" }

{"E3"}
5
1
Returns: { "01110" }

We start at (0,0). We then move east to (1,0), and toggle the state from off to on. We then move east two more times, each time toggling a state, and after 3 moves we have toggled three of the squares to on.

{"E3","W2"}
5
1
Returns: { "00010" }

Again, we move east 3 times and end up at (3,0) with (1,0), (2,0), and (3,0) in the on state. We then move west twice, turning (1,0) and (2,0) to the off state.

{"E7","W2"}
5
1
Returns: { "01001" }

We move east 4 times and turn (1,0), (2,0), (3,0) and (4,0) to on. After this we keep trying to move east, but run into the wall, and so we do nothing. We then go west twice, turning (2,0) and (3,0) to off.

Submissions are judged against all 66 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SketchGame with a public method vector<string> draw(vector<string> moves, int x, int y) · 66 test cases · 2 s / 256 MB per case