Author: Sachin Singh
Tester: Sachin Singh
Editorialist: Sachin Singh
DIFFICULTY:
medium, hard.
PREREQUISITES:
Math,matrix,algorithm.
PROBLEM:
CodeMaster was at home due to lockdown and after long hours of playing regular indoor games, he makes one game named “STEP OR JUMP”. It is like a snake and ladder but there are no ladders but only snakes in the game.
There are only two moves possible in this game, they are:
1.STEP (move 1 cell ahead)
2.JUMP (move 2 cells ahead).
0 1 0 1 0 1 0 0
1 0 0 1 0 1 0 1
1 0 0 1 0 0 0 1
0 0 0 1 0 1 0 0
0 1 0 0 0 0 1 0
0 1 0 0 1 0 0 1
0 0 1 0 0 1 1 0
0 1 0 0 1 0 0 0
The above matrix depicts the game board of order NxN (where N=8). The chain of ones denotes the single snake, there are more than one snakes in-game. The 1’s may be connected by the same column, diagonally(from both side right or left side).
Note:
1.Mouth Of The Snake: The first one on the upper side of the matrix which is not connected to anyone further is called the mouth of the snake.
2.Tail Of The Snake: The last one of the chain denote the tail of the snake.
3.The body or the tail of the snake is not harmful.
The mouths of all snakes are directed to the upper side of the matrix or board. e.g. in the above matrix(with zero-based indexing) the one at cell(0,1) denote the mouth of the snake and its tail is at cell(2,0).similarly one at cell(3,5) denote the mouth of another snake and its tail is at cell(6,6) and rest of the part of snake(i.e.between the mouth and tell is called as the body of the snake.
CodeMaster wants to find if it is possible to reach at the end cell(0,0) from the start cell(N,0) with the help of given 2 types of moves(i.e. step and jump) and without going in the snake’s mouth…!!!
Rest of the rules as the same as the snake-ladder game-
1.traversing as same…in snake ladder game…(i.e. traverse row by row and after completing a row you have to start new row from the same column)
2.and if caught in the snake’s mouth u will reach the tail of the snake.
Help the CodeMaster to find whether is it possible to reach the endpoint without getting caught in snake’s mouth ,if it is possible then print “Yes” otherwise “No”
QUICK EXPLANATION:
Rule No.2 is the key to our problem. That is, we have to find 2 adjacent mouths of the snake. Because we can go almost two cells ahead(i.e.Jump).
we cannot cross two adjacent mouths of snakes without going in mouths. therefore if we get such situations so the answer is no, otherwise yes.
observe following testcase for N=4:start point(3,0) ,end point(3,3).
0 1 1 0
1 0 0 1
1 0 0 1
0 0 0 0
answer = 'No'
EXPLANATION:
SOLUTIONS:
we Quite clear about our solution approach.
Now,
we have to identify which is the snake's mouth first.
for this, we can make one 'ismouth' method which will identify the snake's mouth.
and once we make it work is done almost.
So,
The moral of the story is we have to find the two adjacent snake's mouth in the whole NxN board/matrix.
if we found then print 'No'
else
print 'Yes'
NOTE :
1. If anyone has any query regarding 'Step & Jump' please ask in the comment section.
2. If anyone has a better approach then please share it in the comment section.
Setter's Solution
#include<bits/stdc++.h>
#define N 33
using namespace std;
bool isMouth(int i,int j,int n,int grid[][N]) {
if(grid[i][j]==0)
return 0;
if(i==n-1)
return 1;
if(j==n-1)
return grid[i+1][j]==0 && grid[i+1][j-1]==0;
if(j==0)
return grid[i+1][j]==0 && grid[i+1][j+1]==0;
return grid[i+1][j]==0 && grid[i+1][j-1]==0 && grid[i+1][j+1]==0;
}
void check(int n,int grid[][N]) {
for(int i=0;i<n;i++) {
for(int j=0;j<n-1;j++) {
if(grid[i][j]==1) {
if(isMouth(i, j, n,grid) && isMouth(i, j+1, n,grid)) {
cout<<"No\n";
return;
}
}
}
}
cout<<"Yes\n";
}
void testcase(){
int n;
cin>>n;
int grid[N][N];
for(int i=n-1;i>=0;i--)
for(int j=0;j<n;j++)
cin>>grid[i][j];
check(n,grid);
}
int main(){
int t;
cin>>t;
while(t--)
testcase();
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
#define N 33
using namespace std;
bool isMouth(int i,int j,int n,int grid[][N]) {
if(grid[i][j]==0)
return 0;
if(i==n-1)
return 1;
if(j==n-1)
return grid[i+1][j]==0 && grid[i+1][j-1]==0;
if(j==0)
return grid[i+1][j]==0 && grid[i+1][j+1]==0;
return grid[i+1][j]==0 && grid[i+1][j-1]==0 && grid[i+1][j+1]==0;
}
void check(int n,int grid[][N]) {
for(int i=0;i<n;i++) {
for(int j=0;j<n-1;j++) {
if(grid[i][j]==1) {
if(isMouth(i, j, n,grid) && isMouth(i, j+1, n,grid)) {
cout<<"No\n";
return;
}
}
}
}
cout<<"Yes\n";
}
void testcase(){
int n;
cin>>n;
int grid[N][N];
for(int i=n-1;i>=0;i--)
for(int j=0;j<n;j++)
cin>>grid[i][j];
check(n,grid);
}
int main(){
int t;
cin>>t;
while(t--)
testcase();
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
#define N 33
using namespace std;
bool isMouth(int i,int j,int n,int grid[][N]) {
if(grid[i][j]==0)
return 0;
if(i==n-1)
return 1;
if(j==n-1)
return grid[i+1][j]==0 && grid[i+1][j-1]==0;
if(j==0)
return grid[i+1][j]==0 && grid[i+1][j+1]==0;
return grid[i+1][j]==0 && grid[i+1][j-1]==0 && grid[i+1][j+1]==0;
}
void check(int n,int grid[][N]) {
for(int i=0;i<n;i++) {
for(int j=0;j<n-1;j++) {
if(grid[i][j]==1) {
if(isMouth(i, j, n,grid) && isMouth(i, j+1, n,grid)) {
cout<<"No\n";
return;
}
}
}
}
cout<<"Yes\n";
}
void testcase(){
int n;
cin>>n;
int grid[N][N];
for(int i=n-1;i>=0;i--)
for(int j=0;j<n;j++)
cin>>grid[i][j];
check(n,grid);
}
int main(){
int t;
cin>>t;
while(t--)
testcase();
return 0;
}
)