ধরি m x n একটি গ্রিড দেওয়া আছে যেখানে প্রতিটি সেল 0 (খালি) বা 1 (বাধা)। এক স্টেপে উপ, নিচ, বাম, ডান যেতে পারা যাবে খালি সেলে। (0,0) থেকে (m-1,n-1) যেতে সর্বোচ্চ kটি বাধা অপসারণ করে ন্যূনতম স্টেপ বের করতে হবে। সম্ভব না হলে -1।
ইনপুট গ্রিড এবং k=1 হলে আউটপুট 6।
সমাধানের ধাপসমূহ
ok() ফাংশন দিয়ে কোঅর্ডিনেট ভ্যালিড কিনা চেক করুন
50x50x2000 আকারের dp অ্যারে INT_MAX দিয়ে ফিল করুন
Data স্ট্রাকচার: x, y, k, length
BFS কিউ দিয়ে (0,0,k,0) থেকে শুরু করুন
কিউ প্রসেস করুন: গন্তব্যে পৌঁছলে length ফেরত দিন, 4 ডিরেকশনে যান, বাধা হলে k কমান, dp আপডেট করুন
সম্ভব না হলে -1 ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#include <bits/stdc++.h> using namespace std; int dir [4][2]={{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; int dp[50][50][2000]; struct Data{ int x, y, k, length; Data(int a, int b, int c, int d){ x = a; y = b; k = c; length = d; } }; class Solution { public: void pre(){ for (int i = 0; i < 50; i++) { for (int j = 0; j < 50; j++) { for (int k = 0; k < 2000; k++) { dp[i][j][k] = INT_MAX; } } } } bool ok(int x, int y, int r, int c){ return (x < r && y < c && x >= 0 && y >= 0); } int shortestPath(vector<vector<int> >& grid, int k){ pre(); int r = grid.size(); int c = grid[0].size(); queue<Data> q; Data root(0, 0, k, 0); q.push(root); while (!q.empty()) { Data node = q.front(); q.pop(); int x = node.x; int y = node.y; int k = node.k; int length = node.length; if (x == r - 1 && y == c - 1) return length; length++; for (int i = 0; i < 4; i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; if (nx == r - 1 && ny == c - 1) return length; if (ok(nx, ny, r, c)) { if (grid[nx][ny] == 0) { if (length < dp[nx][ny][k]) { q.push(Data(nx, ny, k, length)); dp[nx][ny][k] = length; } } else { if (k > 0 && length < dp[nx][ny][k]) { q.push(Data(nx, ny, k - 1, length)); dp[nx][ny][k] = length; } } } } } return -1; } }; main(){ Solution ob; vector<vector<int>> v = {{0,0,0},{1,1,0},{0,0,0},{0,1,1}, {0,0,0}}; cout << (ob.shortestPath(v, 1)); }ইনপুট
{{0,0,0},{1,1,0},{0,0,0},{0,1,1},{0,0,0}}আউটপুট
6
