C++-এ মেজের কোর্নার সেল থেকে মিডল সেল পর্যন্ত সব পথ বের করা

সমস্যা

একটি NxN মেজে প্রতিটি সেলে একটি সংখ্যা আছে। কোনো সেল (i,j)- থেকে সেই সংখ্যা n কতটুকু ধাপ চারদিকে (উপরে, নিচে, বাম, ডান) যেতে পারা যায়। চার কনারের যেকোনো একটি থেকে মিডল সেল (N/2, N/2) পর্যন্ত সব সম্ভাব্য পথ প্রিন্ট করুন।

অ্যালগরিদম: DFS + ব্যাকট্র্যাকিং

1. চার কনার পয়েন্ট থেকে আলাদা আলাদা DFS শুরু করুন।
2. visited সেট দিয়ে সাইকেল এড়ান।
3. বর্তমান সেল (x,y)-এর মান val। চার দিকের নতুন সেল: (x±val, y), (x, y±val)।
4. বৈধ সেল হলে visited-এ যোগ করে রিকার্সিভ কল।
5. মিডল সেল পাওয়া গেলে পথ প্রিন্ট করুন।
6. ব্যাকট্র্যাক: visited ও পথ থেকে মুছুন।

C++ কোড (সংক্ষিপ্ত)

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

bool is_ok(set<pair<int,int>>& visited, pair<int,int> pt) {
    return pt.first>=0 && pt.first=0 && pt.second";
        cout << "MIDDLE\n\n"; return;
    }
    int step = maze[curr.first][curr.second];
    for (int i=0; i<4; i++) {
        pair<int,int> nxt = {curr.first + dr[i]*step, curr.second + dc[i]*step};
        if (is_ok(visited, nxt)) {
            visited.insert(nxt);
            path.push_back(nxt);
            solve(maze, path, visited, nxt);
            path.pop_back();
            visited.erase(nxt);
        }
    }
}

int main() {
    int maze[N][N] = { /* 9x9 মেজ ডেটা */ };
    for (int i=0; i<4; i++) {
        pair<int,int> start = { (i<2?0:N-1), (i%2?N-1:0) };
        set<pair<int,int>> vis; list<pair<int,int>> path;
        vis.insert(start); path.push_back(start);
        solve(maze, path, vis, start);
    }
}

নমুনা আউটপুট

(0,0)->(0,3)->(0,7)->(6,7)->(6,3)->(3,3)->(3,4)->(5,4)->(5,2)->(1,2)->(1,7)->(7,7)->(7,1)->(2,1)->(5,1)->(0,1)->(4,1)->(4,4)->MIDDLE
(0,0)->(0,3)->(0,7)->(6,7)->(6,3)->(3,3)->(3,4)->(5,4)->(5,2)->(1,2)->(1,7)->(7,7)->(7,1)->(2,1)->(2,4)->(4,4)->MIDDLE
... (আরও পথগুলো) ...