หาตัวอักษรในเมทริกซ์ที่มีดาว (*) รอบตัวมากที่สุดใน C++

โจทย์

ให้เมทริกซ์ที่เต็มไปด้วยดาว (*) และตัวอักษร ต้องการหาตัวอักษรที่มีดาวรอบตัวมากที่สุด (นับ 8 ทิศทาง) ถ้ามีค่าเท่ากัน ให้เลือกตัวอักษรที่เล็กกว่าตามลำดับเลขอักษร (Lexicographically smaller)

ตัวอย่าง

ในเมทริกซ์ 4x4 ตัวอักษร A และ C มีดาวรอบตัว 7 ดวง (มากที่สุด) A น้อยกว่า C ตามลำดับอักษร → ผลลัพธ์คือ A

วิธีแก้ปัญหา

1. สแกนเมทริกซ์ทุกเซลล์
2. เมื่อเจอตัวอักษร (A-Z) ให้นับดาวรอบตัว 8 ทิศทาง
3. เก็บจำนวนดาวใน unordered_map <char, int>
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