আলোচনাঃ
আমাকে একটা grid দেয়া হবে। আমাকে grid এর source(S) থেকে destination(D) এ যেতে হবে। কিন্তু grid এর কয়েকটা row এর কয়েকটা column এ একটা করে bomb রাখা থাকবে। যেই path
এ কোনো bomb থাকবে না সেই পথ দিয়ে destination এ যেতে হবে। এমন পথ অনেক থাকতে পারে কিন্তু আমাকে fastest route দিয়ে যেতে হবে। তার মানে আমাকে shortest path বের করা লাগবে।
উত্তরঃ
bfs() দিয়ে shortest path বের করা লাগে। dfs() দিয়ে কিছু ক্ষেত্রে সঠিক answer দিলেও এমন case বের করা যায় যেখানে dfs() ভুল উত্তর দিবে। তাই shortest path বের করার জন্য always
bfs() ব্যবহার করা লাগবে যদি given গ্রাফটা একটা graph হয়। tree হলে dfs() দিয়েও shortest path বের করা যায়।
কিন্তু আমাদের তো grid দেয়া আছে তাই bfs() use করাই better.আর যেহেতু কোনো একটা cell এর উপর,নিচ,ডান,বাম check করা লাগবে তাই direction array use করতে পারি। আর shortest path
এর distance হিসাব করার জন্য dist[] নামক array রাখতে পারি।
কিন্তু এই প্রবলেমের tricky part হচ্ছে input এর কোনটা কি সেটা বুঝা। সেটা নিচে চিত্রের মাধ্যমে দেখানো হলো-
প্রথম লাইন হচ্ছে,given grid এ row(10) আর column(10) number.
২য় line এ 9 আছে। তার মানে given grid এর 9টা row আর column এ bomb রাখা থাকবে।
এর পরের 9টা লাইন এ বলা থাকবে যে,grid এর কোন row তে কয়টা bomb আছে এবং bomb গুলো কোন column এ থাকবে।
আমরা যদি, (3,2,1|7) এই উদাহরণটা নিই তাহলে এর row=3, bomb number=2, column=1,7. তার মানে 3no row তে 2টা bomb আছে। আর bomb গুলো আছে 1 আর 7 no column এ।
এরপর last থেকে 3no line এ 0,0 আছে। এটা হচ্ছে starting point.
এরপরের লাইন 9,9. এটা হচ্ছে destination point.
last এ row=0 and column=0 হলে ইনপুট নেয়া বন্ধ করবো। আর row=column=0 থেকে শুরু করা লাগবে কারণ range দেয়া আছে, (0,0) to (R-1,C-1)
এখন bfs() with direction array দিয়ে কিভাবে implement করা লাগে সেটা জানলেই code লেখা যাবে। তাই আগে bfs() জানা লাগবে এই প্রবলেম solve করার জন্য।
last এ dist[des_x][dex_y] print করলেই হবে। কারণ bfs() function আমাকে shortest path বের করে দিবে আমরা জানি। আর destination এ যাওয়ার
এই shortest distance টা থাকবে dist[des_x][dex_y] cell এ।
C++ Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
bool vis[N][N];
#define pii pair<int,int>
int dx[]={0,0,-1,+1};
int dy[]={+1,-1,0,0};
int row,col;
int dist[N][N];
// check is the current cell valid or not
bool isValid(int nx,int ny)
{
return (nx>=0 && nx<row && ny>=0 && ny<col && vis[nx][ny]!=1);
}
void bfs(int x,int y)
{
queue<pii> q;
q.push({x,y});
vis[x][y]=1;
while(!q.empty()){
pii u=q.front();
//int crn_x=u.first;
//int crn_y=u.second;
q.pop();
for(int k=0;k<4;k++){
int nx=u.first+dx[k];
int ny=u.second+dy[k];
if(isValid(nx,ny)){
q.push({nx,ny});
vis[nx][ny]=1;
// store all distances
dist[nx][ny]=dist[u.first][u.second]+1;
}
}
}
}
int main(){
int bombInRow,rowNum,bomb,colNum;
while(cin>>row>>col){
if(row==0 && col==0) break;
cin>>bombInRow;
memset(dist,0,sizeof(dist));
memset(vis,0,sizeof(vis));
for(int i=0;i<bombInRow;i++){
cin>>rowNum>>bomb;
for(int j=0;j<bomb;j++){
cin>>colNum;
vis[rowNum][colNum]=1;
}
}
int startRow,startcol,endRow,endCol;
cin>>startRow>>startcol>>endRow>>endCol;
bfs(startRow,startcol);
cout<<dist[endRow][endCol]<<"\n";
}
}
If you want to use the photo it would also be good to check with the artist beforehand in case it is subject to copyright. Best wishes. Aaren Reggis Sela
Thanks for your suggestion.
Appreciate you sharing, great blog. Really looking forward to read more. Really Cool. Papagena Rafferty Haland
Thanks
Perfectly written written content, Really enjoyed looking through. Jayme Amos Felise
Thanks for your appreciation.
Amazing! Its in fact remarkable paragraph, I have got much clear idea about from this paragraph. Mei Ronald Mouldon
Thanks. Hope you will come back this site again.
If you want to obtain much from this article then you have to apply these methods to your won web site. Merna Broderick Craner
Thanks for your suggestions.
Hi, I want to subscribe for this web site to obtain newest updates, thus where can i do it please help. Amargo Winthrop Fenton
Sorry dear, in my website there is no such option available.
Thank you for your article post. Thanks Again. Much obliged. Mallissa Guy Nissy
You are most welcome:)
Hi there to all, how is all, I think every one is getting more from this site, and your views are nice designed for new users. Meredith Von Megdal
Thanks
Pingback: LightOj - 1259 - Goldbach`s Conjecture - English - Solution - tusher's blog
Pretty! This has been an incredibly wonderful article. Murial Oberon Cutcliffe
Thanks:)
Hi there, I want to subscribe for this website to take most up-to-date updates, therefore where can i do it please help. Karisa Rhys Clyde Kelcie Jasen Herrmann
Sorry Dear,
Right now my site has no such option. Will add soon:)
Link exchange is nothing else but it is only placing the other person’s web site link on your page at appropriate place and
other person will also do similar for you.
May I simply say what a relief to discover someone that
genuinely understands what they are talking about online.
You certainly realize how to bring a problem to
light and make it important. A lot more people must look at this and understand this side of
your story. I can’t believe you are not more popular since you certainly possess the gift.
asmr 0mniartist
Good to know that:)
There is definately a great deal to find out about this
topic. I love all of the points you’ve made. 0mniartist asmr
Thanks.
Every weekend i used to pay a visit this web site, for the reason that i wish for enjoyment,
for the reason that this this website conations truly nice funny data too.
asmr 0mniartist
It’s difficult to find knowledgeable people about this topic, but you seem like you know what you’re talking about!
Thanks asmr 0mniartist
810601 833506I truly dont accept this specific write-up. Nonetheless, I had searched with Google and Ive discovered out that youre correct and I had been thinking within the improper way. Keep on creating top quality material comparable to this. 927074
Thanks.
Pingback: URL