CSKVSRCB-Editorial

editorial
, ,
1

PROBLEM LINK:

PRACTICE
Editorialist: Avishake Maji

DIFFICULTY:

MEDIUM

PREREQUISITES:

Backtracking

PROBLEM:

Chennai Super Kings vs Royal Challenger Bangalore’s match is near. Still 5 days left for the match. Virat Kohli and MS Dhoni decided to play a game where a ball will be given be any player and that player has to pass it to the target player by passing his teammates.
To play this game the players from two team(not necessary there are equal number of players on both the teams) is placed in a 2d matrix fashion.
But there are some rules:

  1. if the position of a player is (i,j) then he can sent it to (i+1,j)th or (i,j+1)th or (i-1,j)th or (i,j-1)th player provided they are from same team
    Chef is a big fun of MS Dhoni and he wants to find whether there exists any path such that CSK wins the game.

Note :

  1. Remember the ball can be given to any player from either of the two team and each player can take the ball atmost once.
    2)If the player of a team having the ball cannot pass the ball to the target position then the opponent team wins.
  2. The initial player and the target player must belong to the same team for the team to win

EXPLANATION:

We are first going to start with the starting position and then move in (i,j+1) or (i+1,j) or (i-1,j) or (i,j-1) position. If we find any obstacle i.e other player we are going to backtrack from the position. We will continue to do these operation until we reached the target element. If could not able to reach the target element from the initial then declare we will declare the opponent team as winner.

SOLUTION:

#include<bits/stdc++.h>
#define MOD 1000000007
#define pb push_back
#define ll long long int
#define ld long double
#define pii pair<int,int>
#define ff first
#define ss second
#define pr1(x) cout<<x<<"\n"
#define pr2(x,y) cout<<x<<" "<<y<<"\n"
#define pr3(x) cout<<to_string(x)<<" "<<x<<"\n"
#define eps (0.000001)

using namespace std; 
void solve(); 
int main() 
{ 
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 

// #ifndef ONLINE_JUDGE 
// 	freopen("input.txt", "r", stdin); 
// 	freopen("error.txt", "w", stderr); 
// 	freopen("output.txt", "w", stdout); 
// #endif 

	int t;
	// int g=0;
	/*is Single Test case?*/ cin >> t; 
	while (t--) { 
		// cout<<"Case #"<<g+1<<": ";
		// g++;
		solve(); 
		// cout << "\n"; 
	} 

	// cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl; 
	return 0; 
} 
bool isValid(int i,int j,int m,int n){
	return (i>=0&&i<m&&j>=0&&j<n);
}
int solve2(vector<vector<int>>&v,vector<vector<int>>&sol,int m,int n,int i,int j,int x,int y,int p){
	if(i==(x-1)&&j==(y-1)){
		if(p==v[x-1][y-1])
		return 1;
		else{
			return 0;		}
	}
	if(!isValid(i,j,m,n))
		return 0;
	if(sol[i][j]==1||v[i][j]!=p)
		return 0;
	sol[i][j]=1;
	int a=solve2(v,sol,m,n,i+1,j,x,y,p);
	int b=solve2(v,sol,m,n,i,j+1,x,y,p);
	int c=solve2(v,sol,m,n,i-1,j,x,y,p);
	int d=solve2(v,sol,m,n,i,j-1,x,y,p);
	if(a||b||c||d)
		return 1;
	sol[i][j]=0;
	return 0;


}
void solve() 
{ 
	ll m,n;
	cin>>m>>n;
	vector<vector<int>>v;
	int p;
	for(int i=0;i<m;i++)
	{
		vector<int>v2;
		for(int j=0;j<n;j++){
			cin>>p;
			v2.pb(p);
		}
		v.pb(v2);
	}
	int x1,y1,x2,y2;
	cin>>x1>>y1;
	cin>>x2>>y2;
	vector<vector<int>>sol(m,vector<int>(n,0));
	int ans=solve2(v,sol,m,n,x1-1,y1-1,x2,y2,v[x1-1][y1-1]);
	if(v[x1-1][y1-1]==1)
	{
		if(ans==1)
			cout<<"1\n";
		else
			cout<<"0\n";
	}
	else{
		if(ans==0)
		cout<<"1\n";
		else
			cout<<"0\n";
	}

}