โปรแกรมตรวจสอบผู้เล่นคนแรกชนะเกม Ghost ใน C++

เกม Ghost: ผู้เล่นสลับกันเพิ่มตัวอักษร ต้องเป็น prefix ของคำในรายการ ใครสะกดคำครบก่อนแพ้ ตรวจสอบผู้เล่นคนแรกชนะได้ไหม

ตัวอย่าง: words=["manage","manager","min"] → True เล่น: m(1)→ma(2)→man(1)→mana(2)→manag(1)→manage(2) แพ้ → ผู้เล่น 1 ชนะ

ขั้นตอนการแก้ปัญหา

1. จัดกลุ่มคำตามตัวอักษรแรก
2. ในแต่ละกลุ่ม หาคำสั้นที่สุด
3. ถ้ามีกลุ่มไหนที่คำสั้นที่สุดมีความยาวคู่ → ผู้เล่น 1 ชนะ (เพราะผู้เล่น 2 จะต้องสะกดจบ)

เหตุผล: ทั้ง 2 เล่น optimal จะเลือกเส้นทางที่ทำให้คู่ต่อสู้แพ้ ความยาวคู่ = ผู้เล่น 2 สะกดตัวสุดท้าย

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

bool solve(vector<string>& words) {
    map<char, set<string>> mp;
    for (auto& w : words) mp[w[0]].insert(w);
    for (auto& p : mp) {
        string shortest = *p.second.begin(); // set เรียงอัตโนมัติ
        if (shortest.size() % 2 == 0) return true;
    }
    return false;
}

int main() {
    vector<string> v = {"manage","manager","min"};
    cout << solve(v); // 1
    return 0;
}

อินพุต

{"manage","manager","min"}

เอาต์พุต

1