ধরুন আমাদের একটি 3x3 বোর্ড আছে যেখানে সমস্ত সংখ্যা 0 থেকে 8 রেঞ্জের মধ্যে রয়েছে এবং কোনো পুনরাবৃত্তি সংখ্যা নেই। এখন, আমরা তার 4 প্রতিবেশীর একটির সাথে 0 অদলবদল করতে পারি, এবং আমরা সমস্ত সাজানো ক্রম পেতে এটি সমাধান করার চেষ্টা করছি, আমাদের লক্ষ্যে পৌঁছানোর জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক পদক্ষেপ খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট মত হয়
| 3 | 1 | 2 |
| 4 | 7 | 5 |
| 6 | 8 | 0 |
তাহলে আউটপুট হবে 4
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন সংজ্ঞায়িত করুন find_next()। এটি নোড গ্রহণ করবে
- চালনা :=একটি মানচিত্র সংজ্ঞায়িত করে প্রতিটি মান {0:[1, 3],1:[0, 2, 4],2:[1, 5],3:[0, 4] এর সাথে সম্পর্কিত একটি তালিকা হিসাবে চলে , 6],4:[1, 3, 5, 7],5:[2, 4, 8],6:[3, 7],7:[4, 6, 8],8:[5, 7 ], }
- ফলাফল :=একটি নতুন তালিকা
- pos_0 :=নোডের প্রথম মান
- প্রতিটি মুভের জন্য [pos_0], করুন
- new_node :=নোড থেকে একটি নতুন তালিকা
- অদলবদল new_node[move] এবং new_node[pos_0]
- ফলাফলের শেষে new_node থেকে একটি নতুন টিপল ঢোকান
- ফলাফল ফেরত দিন
- একটি ফাংশন get_paths() সংজ্ঞায়িত করুন। এটি ডিক্ট নিতে হবে
- cnt :=0
- নিম্নলিখিতটি অসীমভাবে করুন, করুন
- current_nodes :=একটি তালিকা যেখানে মান cnt এর মতই
- যদি বর্তমান_নোডের আকার 0 এর মতো হয়, তাহলে
- রিটার্ন -1
- কারেন্ট_নোডের প্রতিটি নোডের জন্য, করুন
- next_moves :=find_next(node)
- পরবর্তী_চালানোর প্রতিটি পদক্ষেপের জন্য, করুন
- যদি মুভ ডিক্টে উপস্থিত না থাকে, তাহলে
- dict[move] :=cnt + 1
- যদি সরানো একই হয় (0, 1, 2, 3, 4, 5, 6, 7, 8) , তাহলে
- cnt + 1 ফেরত দিন
- cnt :=cnt + 1
- যদি মুভ ডিক্টে উপস্থিত না থাকে, তাহলে
- প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
- ডিক্ট :=একটি নতুন মানচিত্র, সমতল করুন :=একটি নতুন তালিকা
- আমি রেঞ্জ 0 থেকে বোর্ডের সারি গণনার জন্য, করুন
- চ্যাপ্টা :=সমতল + বোর্ড[i]
- ফ্ল্যাটেন :=সমতলের একটি অনুলিপি
- ডিক্ট[ফ্ল্যাটেন] :=0
- যদি সমতল করা হয় (0, 1, 2, 3, 4, 5, 6, 7, 8) , তাহলে
- রিটার্ন 0
- রিটার্ন get_paths(dict)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Solution:
def solve(self, board):
dict = {}
flatten = []
for i in range(len(board)):
flatten += board[i]
flatten = tuple(flatten)
dict[flatten] = 0
if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return 0
return self.get_paths(dict)
def get_paths(self, dict):
cnt = 0
while True:
current_nodes = [x for x in dict if dict[x] == cnt]
if len(current_nodes) == 0:
return -1
for node in current_nodes:
next_moves = self.find_next(node)
for move in next_moves:
if move not in dict:
dict[move] = cnt + 1
if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return cnt + 1
cnt += 1
def find_next(self, node):
moves = {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4, 6],
4: [1, 3, 5, 7],
5: [2, 4, 8],
6: [3, 7],
7: [4, 6, 8],
8: [5, 7],
}
results = []
pos_0 = node.index(0)
for move in moves[pos_0]:
new_node = list(node)
new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
results.append(tuple(new_node))
return results
ob = Solution()
matrix = [
[3, 1, 2],
[4, 7, 5],
[6, 8, 0]
]
print(ob.solve(matrix)) ইনপুট
matrix = [ [3, 1, 2], [4, 7, 5], [6, 8, 0] ]
আউটপুট
4
