CF - 1214D - Treasure Island

 Problem Description here

Problem: সহজ ভাষায় বললে, এই প্রব্লেমে আমাদেরকে একটি গ্রীড দেয়া থাকবে। গ্রীডে দুই ধরণের সেল আছে। একধরনের সেলের উপর দিয়ে যাতায়াত সম্ভব এবং অন্য ধরণের সেলের উপর দিয়ে যাতায়াত সম্ভব নয়। আমাদেরকে বের করতে হবে Upper Left সেল থেকে Lower Right সেলে যাওয়ার জন্য কয়টা পাথ আছে যারা সোর্স এবং ডেস্টিনেশন ব্যাতীত অন্য কোন সেলে মিলিত হয় না। 

এবং আমরা শুধু নিচে অথবা ডানে মুভ দিতে পারবো। 

Solution:

১) একটু ভালোভাবে লক্ষ্য করলে বোঝা যায় যে, উপরোল্লিখিত পাথের সংখ্যা হবে সর্বোচ্চ ২।

২) এখন আমরা একটি ডিএফএস ছেড়ে একটা ভ্যালিড পাথ পাওয়া গেলে সেটি ভিজিট করে ফেলবো।

৩) আবারও ডিএফএস ছেড়ে কোন ভ্যালিড পাথ পাওয়া যায় কি না দেখবো। এক্ষেত্রে পূর্বের প্রাপ্ত(যদি পেয়ে থাকি) পাথের কোন সেল ভিজিট করা যাবে না যদি না সেটি সোর্স অথবা ডেস্টিনেশন সেল না হয়। 

	#include<bits/stdc++.h>
	#define Input freopen("in.txt","r",stdin)
	#define Output freopen("out.txt","w",stdout)
	#define ll long long int
	#define ull unsigned long long int
	#define pii pair<int,int>
	#define pll pair<ll,ll>
	#define sc scanf
	#define scin(x) sc("%d",&(x))
	#define scin2(x,y) sc("%d %d",&(x),&(y))
	#define scln(x) sc("%lld",&(x))
	#define scln2(x,y) sc("%lld %lld",&(x),&(y))
	#define pf printf
	#define ms(a,b) memset(a,b,sizeof(a))
	#define pb(a) push_back(a)
	#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
	using namespace std;
	/** Problem Summary: Find number of non-overlapping path from source to destination **/
	const int fx[] = {+1,+0};
	const int fy[] = {+0,+1};
	int n,m;
	vector<vector<int> >vis;
	vector<vector<char> >grid;
	bool DFS(int sx,int sy)
	{
	if(sx==n-1 && sy==m-1)
	return 1;
	int ret = 0;
	vis[sx][sy] = 1;
	for(int k=0 ; k<2 ; k++){
	int nx = sx+fx[k];
	int ny = sy+fy[k];
	if(nx>=0 && nx<n && ny>=0 && ny<m && grid[nx][ny]=='.' && !vis[nx][ny]){
	ret |= DFS(nx , ny);
	}
	if(ret)
	break;
	}
	return ret;
	}
	void Solve(int t)
	{
	int i,j,k,path=0;
	cin>>n>>m;
	for(i=1 ; i<=n ; i++){
	vector<char>temp;
	vector<int>temp2;
	char ch;
	for(j=1 ; j<=m ; j++){
	cin>>ch;
	temp.pb(ch);
	temp2.pb(0);
	}
	temp2.pb(0);
	grid.pb(temp);
	vis.pb(temp2);
	}
	path += DFS(0 , 0);
	vis[0][0] = vis[n-1][m-1] = 0;
	path += DFS(0 , 0);
	cout<<path<<endl;
	}
	int main()
	{
	int t,T;
	T = 1;
	RUN_CASE(t,T)
	{
	Solve(t);
	}
	return 0;
	}

view raw CF - 1214D.cpp hosted with ❤ by GitHub

 

Similar Problem

Happy Coding 😊