CHAJOE - EDITORIAL

editorial
, ,
1

PROBLEM LINK

Practice

PROBLEM STATEMENT

The F.R.I.E.N.D.S are very bored and sad as they cannot visit ‘Central Perk’ anymore and are stuck in their apartments. So, Joey and Chandler come up with a new game called “Maze Escape”.
  • This is how it works: The Maze is in the form of a rectangular grid. where there are M+1M+1 levels numbered from 0−M0−M and each level has N+1N+1 doors numbered from 0−N0−N, all the doors lead to the same upper level.

Chandler is confident that he doesn’t need to add any traps to the maze and Joey is still going to fail to cross it(cause we all know how smart joey is). Each door of level ‘i’ leads to the next level ‘i+1’ and it is possible to travel vertically at the current level without restrictions. But this time Joey suspects some of the doors must be trapped. So he has formulated a plan to cross the Maze, his plan is an array of Integers C, which tells him which possible doors he can choose at each level. At each level i where 1 <=i<=M C[i] denotes the absolute difference between his previous choice of the door (the door through which he entered the current level) and the current door that he can take.

  • Eg, if he took door 5 at level i-1, and C[i] is 4, then he must take either door number 5+4 = 9 or 5-4= 1, at this level. He can never go outside the grid.
    Joey always chooses his lucky number Jth Door when he enters the Maze at level 0. Count and print the number of doors from which Joey can possibly exit the Maze at the Mth level, or print -1 if it is impossible for Joey to exit given his current plan.

SOLUTION

In this problem , we are required to find the number of possible ways to exit the maze, if we follow the given array C. We can initially fill the whole array with -1 , and then on each level check if it is possible to reach a cell using array C from the previous level. If it is possible, mark all such cells as 0 . perform these steps until you reach the last level. In the last level, all the cells marked as 0 are possible ways to exit from the maze .

SOLUTION CODE

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int maze[1002][1002];
	memset(maze,-1,sizeof(maze));
	int n,m;
	cin >> n >> m;
	int b;
	cin>>b;
	int c[m];
	int count=0;
	for(int i=0;i<m;i++)
	cin>>c[i];
	for(int i=0;i<=n;i++)
	{
		if(i==b)
		{
			maze[0][i]=0;
			
			break;
		}
			
	}
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(maze[i][j]==0)
			{
					if(j-c[i] >=0)
					{
						
						maze[i+1][j-c[i]]=0;

					}
					if(j+c[i] <= n)
					{
						
						maze[i+1][j+c[i]]=0;
					}
						
			}
		}
		
	}
	/*for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
			cout<<maze[i][j]<<" ";
		cout<<"\n";
	}
	*/
	for(int  i=0;i<=n;i++)
	{
		if(maze[m][i]==0)
		count++;
	}
	if(count==0)
	cout<<"-1"<<"\n";
	else
	cout << count << endl;
}