SRM 574 DIV2 250 - ゆずさん研究所

・2次元配列で定義されたcityMapが与えられる。
　各セルには、"."または[A-Z]のいずれかの文字が代入されている。
・cityMap上に出現する文字（A-Z）の出現回数を示す配列（int POIs[]）が与えられる。
　POIsの各要素の値が、どの文字の出現回数を示すものであるかは不明である。
・POIsの各要素の値はユニークである。つまり、cityMapには、出現回数が同じ文字は出現しない。
・配列POIs[]の各要素を、対応する文字に置き換えてできる文字列を返せ。

例えば、cityMapを以下のように定義して、

const char *cityMap[] = 
{".S..RR....",
 "..M..S...M",
 "..RRMR..R.",
 "M....R....",
 "..R.RR..M."}

POIs[]が以下のように与えられたとします。

int POIs[] = {2, 10, 5};

すると、cityMap上に2回出現する文字は"S"、10回出現する文字は"R"、5回出現する文字は"M"となるので、POIsの各要素を、対応する文字に置換してできる文字列は、"SRM"となります。

方針としては、

１．愚直にcityMapを1文字ずつ舐めて、
２．文字と出現回数の対応表（sign_occur_table）を作成する。
３．POIs[]とsign_occur_tableを突き合わせて、文字に変換する。

…という流れになります。

sign_occur_tableについては、構造体配列か二次元配列で、文字-出現回数の対応を格納する…よりも、1次元配列を作成し、配列の要素番号を、「アルファベットのASCIIコード-'A'(0x41)」として管理し、セルの値に出現回数をセットする（つまり連想配列に近い）と、出現回数のカウントアップ時にループを回さなくて済みます（EBCDICなど、アルファベットの文字コードが連続していない文字コードの場合、この持ち方は通用しませんが…）。

  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 #define NUM_OF(array)   (sizeof(array)/sizeof(*array))
  5 
  6 char *CityMap_getLegend(char *answer, const char **cityMap, const size_t map_width, const size_t map_height,
  7                         const int *POIs, const size_t POIs_numof)
  8 {
  9     int sign_occurr_table['Z'-'A' + 1];
 10     int x;
 11     int y;
 12     int i;
 13     int j;
 14     int k = 0;
 15 
 16     memset(sign_occurr_table, 0, sizeof(sign_occurr_table));
 17 
 18     for(y=0; y<map_height; y++){
 19         for(x=0; x<map_width; x++){
 20             if(cityMap[y][x] < (char)'A' || cityMap[y][x] > (char)'Z'){
 21                 continue;
 22             }
 23             sign_occurr_table[cityMap[y][x] - 'A']++;
 24         }
 25     }
 26 
 27     for(i=0; i<POIs_numof; i++){
 28         for(j=0; j<NUM_OF(sign_occurr_table); j++){
 29             if(POIs[i] == sign_occurr_table[j]){
 30                 answer[k++] = (char)(j + 'A');
 31             }
 32         }
 33     }
 34     answer[k] = '\0';
 35 
 36     return answer;
 37 }
 38 
 39 int main(void)
 40 {
 41     char    answer[26+1];
 42     const char *cityMap[] =
 43             {"AIAAARRI.......GOAI.", \
 44              ".O..AIIGI.OAAAGI.A.I", \
 45              ".A.IAAAARI..AI.AAGR.", \
 46              "....IAI..AOIGA.GAIA.", \
 47              "I.AIIIAG...GAR.IIAGA", \
 48              "IA.AOA....I....I.GAA", \
 49              "IOIGRAAAO.AI.AA.RAAA", \
 50              "AI.AAA.AIR.AGRIAAG..", \
 51              "AAAAIAAAI...AAG.RGRA",
 52              ".J.IA...G.A.AA.II.AA"};
 53     const int POIs[] = {16,7,1,35,11,66};
 54 
 55     printf("Returns: %s\n", CityMap_getLegend(answer, cityMap, strlen(cityMap[0]), \
                                NUM_OF(cityMap), POIs, NUM_OF(POIs)));
 56 
 57     return 0;
 58 }