যেকোনো গ্রাফে গেম#

ধরি দুইজন খেলোয়াড় একটি যেকোনো গ্রাফ $G$-তে একটি গেম খেলছে। অর্থাৎ গেমের বর্তমান অবস্থা একটি নির্দিষ্ট ভার্টেক্স। খেলোয়াড়রা পালাক্রমে চাল দেয়, এবং বর্তমান ভার্টেক্স থেকে একটি সংযোগকারী এজ ব্যবহার করে পার্শ্ববর্তী ভার্টেক্সে যায়। গেমের উপর নির্ভর করে, যে ব্যক্তি চাল দিতে পারবে না সে হয় হারবে অথবা জিতবে।

আমরা সবচেয়ে সাধারণ ক্ষেত্র বিবেচনা করি, সাইকেলসহ একটি যেকোনো ডিরেক্টেড গ্রাফের ক্ষেত্র। আমাদের কাজ হলো, প্রদত্ত একটি প্রারম্ভিক অবস্থায়, নির্ধারণ করা যে উভয় খেলোয়াড় অপটিমাল কৌশলে খেললে কে জিতবে, অথবা গেমের ফলাফল ড্র হবে কিনা।

আমরা এই সমস্যাটি অত্যন্ত দক্ষতার সাথে সমাধান করব। আমরা গ্রাফের সব সম্ভাব্য প্রারম্ভিক ভার্টেক্সের জন্য সমাধান খুঁজব এজের সংখ্যার সাপেক্ষে লিনিয়ার সময়ে: $O(m)$।

অ্যালগরিদমের বিবরণ#

আমরা একটি ভার্টেক্সকে জয়ী ভার্টেক্স বলব, যদি এই অবস্থা থেকে শুরু করা খেলোয়াড় অপটিমালভাবে খেললে গেমটি জিতবে (প্রতিপক্ষ যাই চাল দিক না কেন)। একইভাবে, আমরা একটি ভার্টেক্সকে পরাজিত ভার্টেক্স বলব, যদি এই ভার্টেক্স থেকে শুরু করা খেলোয়াড় প্রতিপক্ষ অপটিমালভাবে খেললে হেরে যায়।

গ্রাফের কিছু ভার্টেক্সের জন্য, আমরা আগে থেকেই জানি যে সেগুলো জয়ী বা পরাজিত ভার্টেক্স: যথা সমস্ত ভার্টেক্স যাদের কোনো আউটগোয়িং এজ নেই।

এছাড়াও আমাদের নিম্নলিখিত নিয়মগুলো আছে:

• যদি কোনো ভার্টেক্সের একটি আউটগোয়িং এজ একটি পরাজিত ভার্টেক্সে নিয়ে যায়, তাহলে সেই ভার্টেক্সটি নিজেই একটি জয়ী ভার্টেক্স।
• যদি কোনো ভার্টেক্সের সব আউটগোয়িং এজ জয়ী ভার্টেক্সে নিয়ে যায়, তাহলে সেই ভার্টেক্সটি নিজেই একটি পরাজিত ভার্টেক্স।
• যদি কোনো পর্যায়ে এখনও অনির্ধারিত ভার্টেক্স থাকে, এবং প্রথম বা দ্বিতীয় কোনো নিয়মই প্রযোজ্য না হয়, তাহলে এই প্রতিটি ভার্টেক্স প্রারম্ভিক ভার্টেক্স হিসেবে ব্যবহৃত হলে উভয় খেলোয়াড় অপটিমালভাবে খেললে ড্র হবে।

সুতরাং, আমরা তৎক্ষণাৎ $O(n m)$ সময়ে চলে এমন একটি অ্যালগরিদম সংজ্ঞায়িত করতে পারি। আমরা সব ভার্টেক্সের মধ্য দিয়ে যাই এবং প্রথম বা দ্বিতীয় নিয়ম প্রয়োগের চেষ্টা করি, এবং পুনরাবৃত্তি করি।

তবে, আমরা এই প্রক্রিয়াটিকে ত্বরান্বিত করতে পারি, এবং কমপ্লেক্সিটি $O(m)$-এ নামিয়ে আনতে পারি।

আমরা সেই সব ভার্টেক্সের উপর দিয়ে যাব, যেগুলো প্রাথমিকভাবে জয়ী বা পরাজিত অবস্থা বলে জানি। এদের প্রতিটি থেকে, আমরা একটি ডেপথ ফার্স্ট সার্চ শুরু করব। এই DFS বিপরীত এজ ধরে পিছনে যাবে। প্রথমত, এটি ইতিমধ্যে জয়ী বা পরাজিত হিসেবে নির্ধারিত ভার্টেক্সে প্রবেশ করবে না। এবং আরো, যদি সার্চ একটি পরাজিত ভার্টেক্স থেকে একটি অনির্ধারিত ভার্টেক্সে যায়, তাহলে আমরা এটিকে জয়ী ভার্টেক্স হিসেবে চিহ্নিত করি, এবং এই নতুন ভার্টেক্স ব্যবহার করে DFS চালিয়ে যাই। যদি আমরা একটি জয়ী ভার্টেক্স থেকে একটি অনির্ধারিত ভার্টেক্সে যাই, তাহলে আমাদের পরীক্ষা করতে হবে যে এর থেকে সব এজ জয়ী ভার্টেক্সে যায় কিনা। আমরা প্রতিটি ভার্টেক্সের জন্য জয়ী ভার্টেক্সে যাওয়া এজের সংখ্যা সংরক্ষণ করে $O(1)$-এ এই পরীক্ষাটি করতে পারি। সুতরাং যদি আমরা একটি জয়ী ভার্টেক্স থেকে একটি অনির্ধারিত ভার্টেক্সে যাই, তাহলে আমরা কাউন্টার বাড়াই, এবং পরীক্ষা করি এই সংখ্যা আউটগোয়িং এজের সংখ্যার সমান কিনা। যদি তাই হয়, আমরা এই ভার্টেক্সকে পরাজিত ভার্টেক্স হিসেবে চিহ্নিত করতে পারি, এবং এই ভার্টেক্স থেকে DFS চালিয়ে যেতে পারি। অন্যথায় আমরা এখনও জানি না এই ভার্টেক্সটি জয়ী না পরাজিত, এবং তাই এটি ব্যবহার করে DFS চালিয়ে যাওয়ার কোনো অর্থ নেই।

মোটের উপর আমরা প্রতিটি জয়ী এবং প্রতিটি পরাজিত ভার্টেক্স ঠিক একবার ভিজিট করি (অনির্ধারিত ভার্টেক্স ভিজিট করা হয় না), এবং আমরা প্রতিটি এজও সর্বাধিক একবার অতিক্রম করি। তাই কমপ্লেক্সিটি $O(m)$।

ইমপ্লিমেন্টেশন#

এখানে এমন একটি DFS-এর ইমপ্লিমেন্টেশন দেওয়া হলো। আমরা ধরে নিচ্ছি যে adj_rev ভেরিয়েবলে গ্রাফের বিপরীত আকারে অ্যাডজেসেন্সি লিস্ট সংরক্ষিত, অর্থাৎ গ্রাফের এজ $(i, j)$ সংরক্ষণের বদলে, আমরা $(j, i)$ সংরক্ষণ করি। এছাড়াও প্রতিটি ভার্টেক্সের জন্য আমরা ধরে নিচ্ছি যে আউটগোয়িং ডিগ্রি ইতিমধ্যে হিসাব করা আছে।

vector<vector<int>> adj_rev;

vector<bool> winning;
vector<bool> losing;
vector<bool> visited;
vector<int> degree;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj_rev[v]) {
        if (!visited[u]) {
            if (losing[v])
                winning[u] = true;
            else if (--degree[u] == 0)
                losing[u] = true;
            else
                continue;
            dfs(u);
        }
    }
}

উদাহরণ: “পুলিশ ও চোর”#

এখানে এই ধরনের গেমের একটি নির্দিষ্ট উদাহরণ দেওয়া হলো।

$m \times n$ আকারের একটি বোর্ড আছে। কিছু ঘরে প্রবেশ করা যায় না। পুলিশ অফিসার এবং চোরের প্রাথমিক স্থানাঙ্ক জানা আছে। একটি ঘর হলো বের হওয়ার পথ। যদি পুলিশ এবং চোর যেকোনো মুহূর্তে একই ঘরে থাকে, পুলিশ জিতবে। যদি চোর বের হওয়ার ঘরে থাকে (পুলিশও সেই ঘরে না থাকা অবস্থায়), তাহলে চোর জিতবে। পুলিশ সব ৮ দিকে হাঁটতে পারে, চোর শুধু ৪ দিকে (স্থানাঙ্ক অক্ষ বরাবর)। পুলিশ এবং চোর উভয়ই পালাক্রমে চাল দেবে। তবে তারা চাইলে একটি পালা বাদও দিতে পারে। প্রথম চাল পুলিশের।

এখন আমরা গ্রাফটি তৈরি করব। এর জন্য আমাদের গেমের নিয়মগুলো আনুষ্ঠানিকভাবে প্রকাশ করতে হবে। গেমের বর্তমান অবস্থা নির্ধারিত হয় পুলিশ অফিসারের স্থানাঙ্ক $P$, চোরের স্থানাঙ্ক $T$, এবং কার পালা সেটি দিয়ে, ধরি একে $P_{\text{turn}}$ বলি (যা পুলিশের পালায় true)। সুতরাং গ্রাফের একটি ভার্টেক্স ত্রয়ী $(P, T, P_{\text{turn}})$ দ্বারা নির্ধারিত। এরপর গেমের নিয়ম অনুসরণ করে গ্রাফটি সহজেই তৈরি করা যায়।

এরপর আমাদের নির্ধারণ করতে হবে কোন ভার্টেক্সগুলো প্রাথমিকভাবে জয়ী এবং কোনগুলো পরাজিত। এখানে একটি সূক্ষ্ম বিষয় আছে। জয়ী/পরাজিত ভার্টেক্স স্থানাঙ্কের পাশাপাশি $P_{\text{turn}}$ — কার পালা — এর উপরও নির্ভর করে। যদি পুলিশের পালা হয়, তাহলে ভার্টেক্সটি জয়ী যদি পুলিশ ও চোরের স্থানাঙ্ক মিলে যায়, এবং এটি পরাজিত যদি এটি জয়ী না হয় এবং চোর বের হওয়ার ভার্টেক্সে থাকে। যদি চোরের পালা হয়, তাহলে একটি ভার্টেক্স পরাজিত যদি দুই খেলোয়াড়ের স্থানাঙ্ক মিলে যায়, এবং এটি জয়ী যদি এটি পরাজিত না হয় এবং চোর বের হওয়ার ভার্টেক্সে থাকে।

ইমপ্লিমেন্টের আগে একটি মাত্র বিষয় সিদ্ধান্ত নিতে হবে যে আপনি গ্রাফটি স্পষ্টভাবে তৈরি করতে চান নাকি ফ্লাইতে তৈরি করতে চান। একদিকে, স্পষ্টভাবে গ্রাফ তৈরি করা অনেক সহজ এবং ভুলের সম্ভাবনা কম। অন্যদিকে, এটি কোডের পরিমাণ বাড়াবে এবং রানিং টাইম ফ্লাইতে তৈরির তুলনায় ধীর হবে।

নিম্নলিখিত ইমপ্লিমেন্টেশন স্পষ্টভাবে গ্রাফ তৈরি করবে:

struct State {
    int P, T;
    bool Pstep;
};

vector<State> adj_rev[100][100][2]; // [P][T][Pstep]
bool winning[100][100][2];
bool losing[100][100][2];
bool visited[100][100][2];
int degree[100][100][2];

void dfs(State v) {
    visited[v.P][v.T][v.Pstep] = true;
    for (State u : adj_rev[v.P][v.T][v.Pstep]) {
        if (!visited[u.P][u.T][u.Pstep]) {
            if (losing[v.P][v.T][v.Pstep])
                winning[u.P][u.T][u.Pstep] = true;
            else if (--degree[u.P][u.T][u.Pstep] == 0)
                losing[u.P][u.T][u.Pstep] = true;
            else
                continue;
            dfs(u);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int P = 0; P < n*m; P++) {
        for (int T = 0; T < n*m; T++) {
            for (int Pstep = 0; Pstep <= 1; Pstep++) {
                int Px = P/m, Py = P%m, Tx = T/m, Ty = T%m;
                if (a[Px][Py]=='*' || a[Tx][Ty]=='*')
                    continue;

                bool& win = winning[P][T][Pstep];
                bool& lose = losing[P][T][Pstep];
                if (Pstep) {
                    win = Px==Tx && Py==Ty;
                    lose = !win && a[Tx][Ty] == 'E';
                } else {
                    lose = Px==Tx && Py==Ty;
                    win = !lose && a[Tx][Ty] == 'E';
                }
                if (win || lose)
                    continue;

                State st = {P,T,!Pstep};
                adj_rev[P][T][Pstep].push_back(st);
                st.Pstep = Pstep;
                degree[P][T][Pstep]++;

                const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
                const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
                for (int d = 0; d < (Pstep ? 8 : 4); d++) {
                    int PPx = Px, PPy = Py, TTx = Tx, TTy = Ty;
                    if (Pstep) {
                        PPx += dx[d];
                        PPy += dy[d];
                    } else {
                        TTx += dx[d];
                        TTy += dy[d];
                    }

                    if (PPx >= 0 && PPx < n && PPy >= 0 && PPy < m && a[PPx][PPy] != '*' &&
                        TTx >= 0 && TTx < n && TTy >= 0 && TTy < m && a[TTx][TTy] != '*')
                    {
                        adj_rev[PPx*m+PPy][TTx*m+TTy][!Pstep].push_back(st);
                        ++degree[P][T][Pstep];
                    }
                }
            }
        }
    }

    for (int P = 0; P < n*m; P++) {
        for (int T = 0; T < n*m; T++) {
            for (int Pstep = 0; Pstep <= 1; Pstep++) {
                if ((winning[P][T][Pstep] || losing[P][T][Pstep]) && !visited[P][T][Pstep])
                    dfs({P, T, (bool)Pstep});
            }
        }
    }

    int P_st, T_st;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'P')
                P_st = i*m+j;
            else if (a[i][j] == 'T')
                T_st = i*m+j;
        }
    }

    if (winning[P_st][T_st][true]) {
        cout << "Police catches the thief"  << endl;
    } else if (losing[P_st][T_st][true]) {
        cout << "The thief escapes" << endl;
    } else {
        cout << "Draw" << endl;
    }
}