Romeo and Juliet stay in Rectanglevilla. As the name suggests, Rectanglevilla is indeed a rectangle in shape. Romeo’s current location is marked by ‘s’. Juliet’s current location is marked by ‘d’. In a difficult hour, Romeo has to ensure that he reaches Juliet via the shortest path and hence in shortest time. There are many in Rectanglevilla who are enemies of Romeo and hence will not allow Romeo to pass through their areas. Romeo must avoid these areas while reaching out for Juliet. These areas are marked by ‘w’ character. Areas that Romeo can freely access is marked by ‘-‘ character. Today Romeo needs your help to reach Juliet via shortest path. Help him. The input and output specification sections describe how inputs will be provided on console and how output is expected back on console.
Input Format:
1.First line of input contains grid dimensions delimited by space
character
2. Next rows number of lines contain column number of
characters
3. Valid characters are {s, d, w, -}, where
a.s represents the location of the Romeo
b.d represents the location of the Juliet
c.w represents inaccessible region
d.- represents accessible region
4. End of input is marked by -1 character
Output Format:
1. Output grid should be of the same dimension as the input
grid
2. Output grid should contain path from Romeo’s location s to
Juliet’s location d
3. The ‘s’ character in the grid must be replaced by character ‘a’
to denote that Romeo is actively heading towards Juliet.
Constraints:
1. It is guaranteed that there will always be exactly one
shortest path for Romeo to reach Juliet
Test Cases
Input:
4 4
w – d –
w – w –
w – w w
s – – –
-1
Output:
w – d –
w a w –
w a w w
a – – –
Test Cases
Input:
6 6
s – – – – w
– – – – w –
– – – w – –
– – w – – –
– w – – – –
w – – – – d
-1
Output:
a – – – – w
– a – – w –
– – a w – –
– – w a – –
– w – – a –
w – – – – d
Solution: In C
#include<stdio.h>
int main(){
int n,m,k;
scanf("%d %d",&n,&m);
char ar[n][m];
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
scanf("%c ",&ar[i][j]);
scanf("%d",&k);
int arr[n][m];
int inx,iny,fnx,fny,dir;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(ar[i][j]=='w')
arr[i][j]=0;
else if(ar[i][j]=='-')
arr[i][j]=1;
else if(ar[i][j]=='s') {
inx=i;
iny=j;
arr[i][j]=1;
}
else if (ar[i][j]=='d') {
fnx=i;
fny=j;
arr[i][j]=1;
}
}
}
if(fnx>inx)
dir=1;
else
dir=-1;
int i=inx,j=iny;
arr[i][j]=2;
while(i!=fnx||j!=fny){
if(i==fnx){
arr[i][j+1]=2;
j=j+1;
}
else if(j==fny) {
arr[i+dir][j]=2;
i=i+dir;
}
else if(arr[i+dir][j+1]==1) {
arr[i+dir][j+1]=2;
i=i+dir;
j=j+1;
}
else if(arr[i+dir][j]==1){
arr[i+dir][j]=2;
i=i+dir;
}
else if(arr[i][j+1]==1) {
arr[i][j+1]=2;
j=j+1;
}
}
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++){
if(arr[i][j]==2)
ar[i][j]='a';
ar[fnx][fny]='d';
printf("%c",ar[i][j]);
}
printf("\n");
}
}Also Checkout