SRM574 Div2 Easy "CityMap"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12479
(ダメ)訳
マナ男はある町に初めて訪れた。彼が買った町のマップは、高さH個、幅はW個の
四角形で区切られていた。
それからマナ男はマップに凡例が書かれていないことに気付いた。
全ての主要な場所("POIs"と呼ぶ)の凡例のリストが、マップに載っていた(?)
主要な場所はそれぞれマップ上でシンボルと対応付けられて記載されている。
例えば地下鉄は M という文字に、レストランはフォークとスプーンの絵として書かれている。
幸いな事に、情報が全然ない訳ではなく、凡例の概要が書かれていた。
その概要とは主要な場所のそれぞれの総数であった。
(例えば、レストラン...9 地下鉄...4など)
そして、その総数は同じ数が2つと無いことが分かった。
マナ男はこの概要から、どの記号がどんな場所を表しているかを判断する事にした。
(例えば、地図上の4つの三角形の記号は、おそらく地下鉄を表しているのだろう。など)
あなたは長さ H でそれぞれ W 個の文字が含まれているStringの配列 cityMapが
与えられる。
それぞれの文字は地図上の区切られた四角形に対応しており、その地区がもし道であれば
' . 'が、主要な場所(POI)であれば大文字のアルファベットが書かれている。
違うPOIは違ったアルファベットになっているし、同じPOIは同じアルファベットになっている。
あなたはまたintの配列 POIsが与えられる。
POIs[i]は i 番目のPOIが何個地図上にあるかを意味する。
それは地図上にその個数だけある記号が必ず存在する事が保証される。
つまり、cityMapに違う文字が同じ回数だけ出現することはないし、
POIsに間違った個数が入っていることはない。
各POIにはどの文字が対応するのかを決定せよ。
そして、i番目にあるPOIに対応する文字をi番目とした文字列を返せ。
制約
1 <= H, W <= 50
1 <= POIsの長さ <= 26
考えた事
問題文ながっ
めんどいからサンプルだけ見て解いた。
ソースコード
class CityMap { public: string getLegend(vector <string> cityMap, vector <int> POIs){ int signs[26]; for( int i = 0; i < 26; i++ ){ signs[i] = 0; } int h = cityMap.size(); int w = cityMap[0].length(); for( int y = 0; y < h; y++ ){ for( int x = 0; x < w; x++ ){ char c = cityMap[y][x]; if( c == '.' ) continue; int id = c - 'A'; signs[id]++; } } ostringstream oss; for( int i = 0; i < POIs.size(); i++ ){ for( int j = 0; j < 26; j++ ){ if( POIs[i] == signs[j] ){ char c = j + 'A'; oss << c; } } } return oss.str(); } };