Exit Point in a Matrix | Samsung
Exit Point in a Matrix
Write a program to find the exit point in a matrix. Given a 3*3 matrix with 0’s and 1’s, you enter the matrix at cell(0,0) in left to right direction. Whenever a 0 you retain in the same direction if you encounter a 1’s you have to turn right of the current direction. You have to find from which index you will leave the matrix at the end. That index is the exit point in a matrix.
Logic
- The logic is simple. Pass the array, row index and column to the function endpoint().
- We start from index (0,0) in left to right direction.
- If we encounter 1, turn right direction.
- When we reach the end of the matrix, print the index and exit the program.
Algorithm
- In endpoint function, at first we move from left to right by keeping row index(i) constant and incrementing column.
- If we encounter 1, move from top to bottom by keeping column index(j) constant and incrementing row.
- Again if we see 1, move from right to left till we reach the end of the matrix.
- If we encounter 1 again we have to move from left to right so we make a recursive call to endpoint function passing row and column+1 as an argument.
Program
#include<stdio.h>
#include<stdlib.h>
int main()
{
int st=0,en=0;
int arr[][3]={{0,0,1},{0,0,0},{0,0,1}};
endpoint(st,en,arr); //Passing 3*3 array
}
void endpoint(int r, int c, int arr[][3])
{
int m=3,n=3,i=r,j=c;
// m- row size n- column size
/*Moving from left to right
starting from 0,0*/
for(j=c;j<n;j++)
{
/*if found 0 in matrix*/
if(arr[i][j]!=1)
{
/*Matrix column end reached*/
if(j==n-1)
{
printf("%d %d",i,j);
exit(0); //end the program
}
continue; //continue if element is not 1
}
/*if found 1 then turn right*/
else
{
/*Moving from top to bottom*/
for(i=r+1;i<m;i++)
{
if(arr[i][j]!=1)
{
/*Matrix row reached end*/
if(i==m-1)
{
printf("%d %d",i,j);
exit(0);
}
continue;
}
/*found 1 turn right*/
else{
/*Special case when 1 is in first column
EX: {1,0,0
1,0,0
0,0,0}*/
if(j==0)
{
printf("%d %d",i,j);
exit(0);
}
/*Moving from right to left*/
for(j=j-1;j>=0;j--)
{
if(arr[i][j]!=1)
{
if(j==0)
{
printf("%d %d",i,j);
exit(0);
}
continue;
}
else
{
/*Moving from bottom to top*/
for(i=i-1;i>=0;i--)
{
if(arr[i][j]!=1)
{
if(i==0)
{
printf("%d %d",i,j);
exit(0);
}
continue;
}
/*Again left to right so recursive call*/
else
{
//with same row, column+1
endpoint(i,j+1,arr);
}
}
}
}
}
}
}
}
}
