QueenCovering

TCCC06 Spon 1 · 2006-08-22 · by Cosmin.ro

TCCC06 Spon 1 · 2006-08-22 · by Cosmin.ro · Brute Force

Show categories

Class Name: QueenCovering

Return Type: String

Method Name: getPlacement

Arg Types: (vector<string>)

Problem Statement

You are given an 8 x 8 chessboard, and you must place the minimum possible number of queens onto the board such that all cells are under attack from at least one queen, and no queens attack each other. Some of the cells on the board are destroyed. A queen cannot be placed on a destroyed cell, and destroyed cells don't need to be under attack. A queen attacks a cell if it is in the same row, same column, or same diagonal as that cell (even if there are destroyed cells between them). Rows are labelled from 1 to 8 and columns from 'A' to 'H'.

You are given a String[] board, where the jth character of the ith element represents the cell at row i, column j. A '.' denotes an empty cell, and a '#' denotes a destroyed cell. A solution is represented by a string which concatenates the positions of the queens. Each queen will be represented by two characters rc, where r is the row label and c is the column label. For example, if the solution contains one queen at row 1, column H and another at row 5, column C, it can be represented as "1H5C" or "5C1H". If there are several solutions which use the minimal number of queens, return the one that comes first lexicographically.

Constraints

board will have exactly 8 elements.
Each element of board will contain exactly 8 characters.
Each character of board will be either '.' or '#'.

Examples

{
  "........",
  "..######",
  ".#.#####",
  ".##.####",
  ".###.###",
  ".####.##",
  ".#####.#",
  "........"}
Returns: "1A8B"

We place one queen on the first row and the first column, and another queen on the last row and on the second column.

{
 "#......#",
 ".#......",
 "..#...#.",
 "........",
 "..#.....",
 "..#..#..",
 "#.......",
 "#...###."}
Returns: "1B2D3A4C5E"

{
 "........",
 "........",
 "........",
 "........",
 "........",
 "........",
 "........",
 "........"}
Returns: "1A2C3E4B5D"

{
  "..##.##.",
  ".###..##",
  "##..###.",
  "#..#...#",
  ".#.##.#.",
  "#...##..",
  "#..#####",
  "..#..#.#"}
Returns: "1A4C5H6B"

{
  "##..###.",
  "#######.",
  "######.#",
  "#####.#.",
  "#####.##",
  "#.####..",
  "#####...",
  "#..####."}
Returns: "1C2H6G"

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

Coding Area

Language: C++17 · define a public class QueenCovering with a public method string getPlacement(vector<string> board) · 38 test cases · 2 s / 256 MB per case