C++で行列内の周囲に最も多くの星を持つアルファベットを検索する方法

問題の概要

星（*）とアルファベットが混在した行列 M が与えられたとします。この中から、周囲に最も多くの星を持つアルファベットを見つける必要があります。例えば、次のような行列を考えてみましょう。

この例では、A と C の周囲にはそれぞれ7つの星があり、これが最大値となっています。ただし、複数の文字で星の数が同じ場合は、辞書順（レキシコグラフィカル順）でより小さい文字が出力されます。A は C よりも辞書順で小さいため、この場合の出力は「A」になります。

解決アプローチ

この問題の解き方は非常にシンプルです。以下の手順で処理を進めます。

1. 行列全体を走査し、アルファベットのセルを見つけます。
2. 文字が見つかったら、その周囲8方向（上下左右＋斜め4方向）にある星の数をカウントします。
3. 各文字と対応する星の数を unordered_map に保存します。
4. マップの中から星の数が最大の文字を取り出して出力します。同数の場合は、辞書順で小さい方の文字を採用します。

C++での実装例

#include <iostream>
#include<unordered_map>
#define MAX 4
using namespace std;
int checkStarCount(int mat[][MAX], int i, int j, int n) {
   int count = 0;
   int move_row[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
   int move_col[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
   for (int k = 0; k < 8; k++) {
      int x = i + move_row[k];
      int y = j + move_col[k];
      if (x >= 0 && x < n && y >= 0 && y < n && mat[x][y] == '*')
      count++;
   }
   return count;
}
char charWithMaxStar(int mat[][4], int n) {
   unordered_map<char, int> star_count_map;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         if ((mat[i][j] - 'A') >= 0 && (mat[i][j] - 'A') < 26) {
            int stars = checkStarCount(mat, i, j, n);
            star_count_map[mat[i][j]] = stars;
         }
      }
   }
   int max = -1;
   char result = 'Z' + 1;
   for (auto x : star_count_map) {
      if (x.second > max || (x.second == max && x.first < result)) {
         max = x.second;
         result = x.first;
      }
   }
   return result;
}
int main() {
   int mat[][4] = {
      { 'B', '*', '*', '*' },
      { '*', '*', 'C', '*' },
      { '*', 'A', '*', '*' },
      { '*', '*', '*', 'D' }
   };
   int n = 4;
   cout << charWithMaxStar(mat, n) << " has maximum amount of stars around it";
}

出力結果

A has maximum amount of stars around it

コードのポイント

checkStarCount 関数では、move_row と move_col の2つの配列を使って、対象セルの周囲8方向を効率的にチェックしています。境界条件（x >= 0 && x < n && y >= 0 && y < n）を設けることで、行列の範囲外へアクセスするのを防いでいます。

また、charWithMaxStar 関数では、(mat[i][j] - 'A') >= 0 && (mat[i][j] - 'A') < 26 という判定により、そのセルが大文字のアルファベットかどうかを確認しています。最終的な比較処理では、星の数が現在の最大値より大きい場合、または同数でかつ辞書順でより小さい文字の場合に結果を更新することで、「最大の星の数を持ち、かつ辞書順で最小の文字」を正しく求められるようにしています。

計算量について見てみると、行列の各セルに対して最大8方向のチェックを行うため、全体の時間計算量は O(n²) となります。ここで n は行列の一辺のサイズです。空間計算量は、文字ごとのカウントを保存するマップ分のみなので O(26)＝O(1) とみなせます。