মনেকর, কোন প্রোগ্রামিং প্রতিযোগিতায় আমাদের সবার ফেভারিট Snake Game সম্পর্কিত একটি প্রব্লেম দেয়া হল। প্রব্লেমটিতে একটি এরিয়ার কথা বলা হয়েছে যেখানে কিছু খাবার আছে। তোমাকে সাপটি মোট কতটি খাবার খেতে পারবে তা বের করতে বলা হয়েছে। প্রব্লেমটি কিভাবে সল্ভ করবে ??? প্রব্লেমটি খুব সহজেই Flood-Fill এলগোরিদম ব্যবহার করে সল্ভ করা যায়।
Flood-Fill এলগোরিদম যেকোন এরিয়াতে ভিজিট করতে সাহায্য করে। সাধারণত উল্লেখিত এরিয়াটি মূলত একটি ম্যাট্রিক্স যাতে প্রতিটি সেল একে-অপরের সাথে যুক্ত। Multi Dimensional Array দিয়ে তুমি এই ম্যাট্রিক্সটি সহজেই বানাতে পারো। তোমরা গ্রাফের টিউটোরিয়ালে নোড ও এজ সম্পর্কে ধারণা পেয়েছো। এখানে প্রতিটি সেলকে গ্রাফের নোড হিসেবে বিবেচনা করলে Flood-Fill এলগোরিদম তোমার জন্য সহজ হয়ে যাবে।
এখন একটি ম্যাট্রিক্স কল্পনা করো যার যে কোন একটি সেল (x,y) এর কো-অর্ডিনেট (0,0) হলে, সেই সেল থেকে চার দিকে অর্থাৎ উপরে-নিচে, ডানে-বামে আমরা (x-1, y), (x+1, y), (x, y+1) ও (x, y-1) এই সেলগুলোতে যেতে পারব কারণ এই সেলগুলো (x,y) এর সাথে যুক্ত।
একইভাবে আমরা যদি আট দিকে অর্থাৎ সব ডিরেকশনে যেতে চাই তাহলে সেল (x,y) থেকে (x-1, y-1), (x-1, y), (x-1, y+1), (x, y-1), (x, y+1), (x+1, y-1), (x+1, y) ও (x+1, y+1) এই সেলগুলোতে যেতে পারব।
এখন প্রোগ্রামিং প্রবলেম রিলেটেড কথায় আসি। মনেকর, Snake Games রিলেটেড একটি প্রব্লেমে তোমাকে একটি ম্যাটিক্স দেয়া হলো, তোমাকে সাপটির Starting সেল বলে দেয়া হল এবং সাপটি কতটি খাবার খেতে পারে তা বের করতে বলা হল। এখন প্রতিটি সেলকে নোড হিসেবে বিবেচনা কর। আমরা ডিএফএস এলগোরিদম থেকে তা জেনেছি যে - যেকোন নোডের সাথে যুক্ত প্রতিটি নোডে ট্রাভার্স করা যায়। এভাবে আমরা ডিএফএস এলগোরিদম ব্যবহার করে Starting সেলের বা নোডের সাথে যুক্ত সব সেলে বা নোডে ট্রাভার্স করবো এবং কোনো নোডে খাবার পেলে তা কাউন্ট করব। অনেক সহজ না ???? নিচে Flood-Fill এর জন্য ডিএফএস এর কোড দেয়া হল-
Code:
Code:
/* DFS-Maze */
#include<bits/stdc++.h>
using namespace std;
int xx[]= {1,-1,0,0}; //For 4 direction
int yy[]= {0,0,1,-1}; // For 4 directions
/*int xx[]= {0,0,1,1,-1,-1,1,-1}; //For 8 direction
int yy[]= {1,-1,1,-1,1,-1,0,0}; // For 8 direction*/
char s[105][105];
bool visit[105][105];
long long int sx,sy,r,c;
bool dfs(long long int ux,long long int uy)
{
bool ret=0;
if(s[ux][uy]=='D')
{
return 1; //destination found
}
for(int i=0; i<4; i++)
{
int vx=ux+xx[i];
int vy=uy+yy[i];
if(vx<0 || vy<0 || vx>=r || vy>=c)
continue;
if(visit[vx][vy]==1 || s[vx][vy]=='#')
continue;
visit[vx][vy]=1;
ret = ret || dfs(vx,vy);
}
return ret;
}
int main()
{
long long int i,j,k;
scanf("%lld%lld", &r, &c);
for(i=0; i<r; i++)
{
scanf("%s",s[i]);
for(j=0; j<c; j++)
{
if(s[i][j]=='S')
{
sx=i;
sy=j;
}
}
}
visit[sx][sy]=1;
if(dfs(sx,sy)==1)
{
printf("yes");
}
else
{
printf("no");
}
return 0;
}
/*
Input:
3 4
S.#.
.#D.
....
*/
এবার আরেকটি প্রোগ্রামিং প্রব্লেম রিলেটেড আলোচনায় আসি। মনেকর, দিপু বিশ্ববিদ্যালয় থেকে বাড়ি যাবে। তোমাকে একটি ম্যাট্রিক্স দেয়া হল যাতে দিপুর বিশ্ববিদ্যালয়ের লোকেশন নোড দেয়া আছে এবং তার বাড়ির লোকেশন নোড দেয়া আছে। তার বিশ্ববিদ্যালয় থেকে বাড়ি যাওয়ার অনেক গুলো পথ আছে। অল্প সময়ে দিপু কত দূরত্ব অতিক্রম করে বাড়ি পৌঁছাতে পারে তা বের করতে বলা হলো তোমাকে। তুমি কিভাবে করবে??? তোমাকে বলা হয়েছে নূন্যতম দূরত্ব বা শর্টেস্ট পাথ বের করতে। যে কোন নোড থেকে অন্য যেকোন নোডের শর্টেস্ট পাথ বের করার পদ্ধতি আমরা বিএফএস এলগোরিদম থেকে জেনেছি। এভাবে বিএফএস এলগোরিদম ব্যবহার করে যেকোন ম্যাট্রিক্সে শর্টেস্ট পাথ খুব সহজেই বের করা যায়। নিচে Flood-Fill এর জন্য বিএফএস এর কোড দেয়া হল-
Code:
Code:
/* BFS-Maze */
#include<bits/stdc++.h>
using namespace std;
int xx[]= {1,-1,0,0}; //For 4 direction
int yy[]= {0,0,1,-1}; // For 4 directions
/*int xx[]= {0,0,1,1,-1,-1,1,-1}; //For 8 direction
int yy[]= {1,-1,1,-1,1,-1,0,0}; // For 8 direction*/
char s[105][105];
bool visit[105][105];
int dis[100][100];
long long int sx,sy,r,c;
queue <long long int> q1;
queue <long long int> q2;
int bfs(long long int ux,long long int uy)
{
long long int ux1, uy1, vx1, vy1;
q1.push(ux);
q2.push(uy);
visit[ux][uy]=1;
while(!q1.empty() && !q2.empty())
{
ux1=q1.front();
uy1=q2.front();
q1.pop();
q2.pop();
if(s[ux1][uy1]=='D')
{
return dis[ux1][uy1]; //destination found
}
for(int i=0; i<4; i++)
{
int vx=ux1+xx[i];
int vy=uy1+yy[i];
if(vx<0 || vy<0 || vx>=r || vy>=c)
continue;
if(visit[vx][vy]==1 || s[vx][vy]=='#')
continue;
visit[vx][vy]=1;
q1.push(vx);
q2.push(vy);
dis[vx][vy]=dis[ux1][uy1]+1;
}
}
}
int main()
{
long long int i, j, d1;
scanf("%lld%lld", &r, &c);
for(i=0; i<r; i++)
{
scanf("%s",s[i]);
for(j=0; j<c; j++)
{
if(s[i][j]=='S')
{
sx=i;
sy=j;
}
}
}
d1=bfs(sx, sy);
printf("%lld", d1);
return 0;
}
প্রোগ্রামিং প্রবলেম :
No comments:
Post a Comment