BarbarianInvasion

SRM 433 · 2009-01-21 · by gojira_tc

SRM 433 · 2009-01-21 · by gojira_tc · Graph Theory

Show categories

Class Name: BarbarianInvasion

Return Type: int

Method Name: minimalDetachment

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

Problem Statement

A kingdom is being threatened by a barbarian invasion from all sides. It was decided that the aggressors must not reach the capital. You are given a String[] countryMap containing a map of the kingdom. The kingdom is represented as a rectangular grid of equal squares. The j-th character of the i-th element of countryMap corresponds to the square at row i, column j. The capital square is marked with a '*', impassable squares are marked with '-', and all other squares are marked with uppercase letters representing different types of open terrain.

You must deploy detachments to open squares in such a way that the capital square is unreachable from the border. In other words, to ensure that no aggressors can reach the capital, each path from the border to the capital must be blocked by an impassable square or a detachment. The enemy can only move directly north, east, south and west between open squares that share common sides. Therefore, only consider paths where each pair of consecutive squares has a common side.

Each type of terrain requires a detachment of a certain size. You are given a int[] detachmentSize, where element 0 is the size of a detachment required for each square of terrain type 'A', element 1 is the required size for terrain type 'B', and so on. Each detachment contains a commander, and qualified commanders are hard to come by. Therefore, your primary goal is to minimize the total number of detachments required. If there are multiple ways to defend the capital using the minimum possible number of detachments, choose the one among them that minimizes the total size of all the detachments. Return the total size of all the detachments.

Constraints

countryMap will contain between 3 and 50 elements, inclusive.
Each element of countryMap will contain between 3 and 50 elements, inclusive.
Elements of countryMap will be of the same length.
Each element of countryMap will contain only uppercase letters, minus signs and asterisks ('A'-'Z','-','*').
countryMap will contain exactly one character '*'.
The '*' character will not be in the first or last row or column of countryMap.
detachmentSize will contain exactly 26 elements.
Each element of detachmentSize will be between 1 and 1000000, inclusive.

Examples

{"ABA",
 "A*A",
 "AAA"}
{1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 5

We have no other way than blocking the squares adjacent to the capital, so the minimal total size of the detachments is 5.

{"CCCC",
 "-BAC",
 "-*AC",
 "--AC"}
{5,20,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 25

Having enough commanders, it could be possible to block the way with 7 detachments standing on the border with the total size of 7. But our primary goal is to minimize the number of detachments, so we have to block 'B' and 'A' squares adjacent to the capital.

{"A----A",
 "-AAAA-",
 "-AA*A-",
 "-AAAA-",
 "A----A"}
{9,8,2,5,3,2,1,2,6,10,4,6,7,1,7,8,8,8,2,9,7,6,5,1,5,10}
Returns: 0

There is already no way to reach the capital from the border.

{"-A-----",
 "-BCCC*-",
 "-A-----"}
{1,5,10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: 5

Blocking 'B' is the optimal decision.

{"WANNABRUTEFORCEMEHUH",
 "ASUDQWNHIOCASFIUQISA",
 "UWQD-ASFFC-AJSQOOWE-",
 "-----*Y--AVSSFIUQISA",
 "UWQD-ASFFC-AJSQOOWE-",
 "JUFDIFD-CHBVISBOOWE-",
 "WANNABRUTEFORCEMEHUH"}
{87,78,20,43,30,12,9,18,57,93,32,60,64,9,69,74,74,78,12,81,63,57,48,8,44,95}
Returns: 218

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

Coding Area

Language: C++17 · define a public class BarbarianInvasion with a public method int minimalDetachment(vector<string> countryMap, vector<int> detachmentSize) · 77 test cases · 2 s / 256 MB per case