Connection Status:
Competition Arena > Cubism

Cubism

SRM 172 · 2003-11-20 · by Eeyore

SRM 172 · 2003-11-20 · by Eeyore · Brute Force, Search
Class Name: Cubism
Return Type: int
Method Name: lines
Arg Types: (vector<string>, string)
Problem Statement

Problem Statement

64 cubes are packed into a four-by-four-by-four lattice. (No, not the kind used to make salad. Forget lettuce! Think of a three-dimensional grid.) Each cube is either black or white.

The lattice configuration is described by a String[] containing four elements of 16 characters each. Imagine the lattice resting on a table with one face oriented north. If we cut the lattice into four slices parallel to the tabletop, then the first String describes the topmost slice, the second describes the second slice from the top, and so on. Each String lists the contents of a slice row by row from north to south, and from west to east within each row. Every character has one of two values: "B" stands for a black cube, "W" for a white one.

We say that a line consists of four cubes, all the same color, arranged sequentially in any orthogonal or diagonal direction. A line may be such that consecutive cubes touch each other with their faces, or such that they touch with their edges, or such that they touch with their corners. All four cubes must be aligned in the same direction. Two lines are distinct if they are not formed of the same four cubes.

Given a lattice configuration and a color, count the number of distinct lines formed by cubes of that color.

Constraints

  • lattice contains exactly four elements
  • each element of lattice is exactly 16 characters long
  • each character is either 'B' or 'W'
  • color is either "black" or "white"
Examples
0)
{"BBBBBWWWBWWWBWWW",
 "BWWWWWWWWWWWWWWW",
 "BWWWWWWWWWWWWWWW",
 "BWWWWWWWWWWWWWWW"}
"black"
Returns: 3

Black lines lie along three edges of the lattice and meet at a corner.

1)
{"BWWWWWWWWWWWWWWW",
 "WWWWWBWWWWWWWWWW",
 "WWWWWWWWWWBWWWWW",
 "WWWWWWWWWWWWWWWB"}
"black"
Returns: 1

A black line stretches diagonally between two corners, its endpoints as far apart as any two cubes of the lattice can be.

2)
{"WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW"}
"black"
Returns: 0

There are no black lines here.

3)
{"WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW",
 "WWWWWWWWWWWWWWWW"}
"white"
Returns: 76

This is the greatest number of lines possible in a lattice.

4)
{"WWWWWWWWWBWWWWWW",
 "WWWBWWWWWWWWWWWW",
 "WWWWWWWWWWWWBWWW",
 "WWWBWWWWWWWWWWWW"}
"white"
Returns: 58

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

Coding Area

Language: C++17 · define a public class Cubism with a public method int lines(vector<string> lattice, string color) · 102 test cases · 2 s / 256 MB per case

Submitting as anonymous